我要评论题意：
给定一棵n个节点的树，树边有边权
现在有k个坏点，要求删除树中若干条边，满足k个坏点两两不连通，问删除的最小边权和是多少
数据范围：n<=1e5
解法：
反过来想，将问题转化为计算能保留的最大边权和
根据kruskal算法思想贪心地对边按边权从大到小排序，然后遍历，
如果当前边不会令两个坏点相连那么可以保留，否则必须删
累加必须删的边的边权就能得到答案。
判断连接之后是否会使两个坏点相连可以用带权并查集维护连通块内坏点数量
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e5+5;
struct Node{
int a,b,c;
}e[maxm];
int pre[maxm];
int cnt[maxm];
int mark[maxm];
bool cmp(Node a,Node b){
return a.c>b.c;
}
int ffind(int x){
return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
signed main(){
ios::sync_with_stdio(0);
int T;cin>>T;
while(T--){
//input
int n,k;cin>>n>>k;
for(int i=1;i<n;i++){
cin>>e[i].a>>e[i].b>>e[i].c;
}
for(int i=0;i<n;i++)mark[i]=0;
for(int i=1;i<=k;i++){
int x;cin>>x;
mark[x]=1;
}
for(int i=0;i<n;i++){
pre[i]=i;cnt[i]=mark[i];
}
//
sort(e+1,e+1+n-1,cmp);
int ans=0;
for(int i=1;i<n;i++){
int x=ffind(e[i].a);
int y=ffind(e[i].b);
if(x!=y){
if(cnt[x]&&cnt[y]){
ans+=e[i].c;
}else{
pre[x]=y;
cnt[y]+=cnt[x];
}
}
}
cout<<ans<<endl;
}
return 0;
}
本文地址：https://blog.csdn.net/weixin_44178736/article/details/107162611
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论