一开始以为题很难，当我坐下来认真读题后，却神奇地发现这道题很水……
这和Kruskal有什么区别啊？
于是我开开心心地十五分种敲完了代码~
然后我就Wa了……
emmm……
尴尬……
一开始我对于每一个点的no[]值都进行维护，时间复杂度特别高，于是就Wa了qwq
后来我发现，其实一颗树只要维护一个no，即根结点的no即可，这样判断这棵树数是否包含那k个城市的时候。只要看根节点就可以了。
那么对于树的相连，看哪一棵树的根节点有no，就继续作为根节点；如果都没有，直接加边就可以，如果都有，这条边就不能连啦~
简单地总结一下，先贪心排序，再正常连边，判断是否能连，一访问到no就直接将其作为根结点，便于以后的访问。
还有，开long long（别问我是怎么知道的）……
其实写代码的时候注意到有关no转移的技巧，这就是一道提高减的题，根本没什么难度。
上代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define maxn 100005 #define int long long struct data { int x,y,w; } q[maxn]; int n,k,sum,par[maxn]; bool no[maxn],flag; bool cmp(data a,data b) { return a.w>b.w; } int find(int x) { if(x==par[x]) return x; return par[x]=find(par[x]); } main() { scanf("%lld%lld",&n,&k); for(int i=0; i<n; i++) par[i]=i; for(int i=0; i<k; i++) { int a; scanf("%lld",&a); no[a]=1; } for(int i=0; i<n-1; i++) { int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); q[i].x=a; q[i].y=b; q[i].w=c; } sort(q,q+n-1,cmp); for(int i=0; i<n-1; i++) { if(no[find(q[i].x)]&&no[find(q[i].y)]) { sum+=q[i].w; continue; } int nx=find(q[i].x); int ny=find(q[i].y); if(no[ny]) par[nx]=ny; else par[ny]=nx; } printf("%lld",sum); return 0; }