由于 QQ 登不上,所以没法在答疑群里提问。
RT,按照第一篇题解的思路,想知道为什么在判断是否连接时要判断一条边的两个节点的祖先是否都是敌人节点或和敌人节点相连,即被标记的节点。而不是这两个节点本身?(在代码中已做标记)
附:代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long n,k,sum;
struct edge{
long long u,v,w;
}e[maxn];
bool cmp(edge xx,edge yy){
return xx.w>yy.w;
}
int f[maxn];
bool vis[maxn];
int find(int x){
return f[x]==x ? x : find(f[x]);
}
int main(){
cin>>n>>k;
for(int i=0;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++){
long long x;
cin>>x;
vis[x]=true;
}
for(int i=1;i<n;i++){
long long u,v,w;
cin>>u>>v>>w;
e[i]={u,v,w};
sum+=w;
}
sort(e+1,e+n,cmp);
for(int i=1;i<n;i++){
int x=find(e[i].u),y=find(e[i].v);//指这一行
if(x==y) continue;//指这一行
if(vis[x] && vis[y]) continue;//指这一行
if(vis[x] || vis[y]) vis[x]=true,vis[y]=true;//指这一行
sum-=e[i].w;
f[find(x)]=find(y);
}
cout<<sum<<"\n";
return 0;
}