题意：现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，
现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开；
简单来说，就是把一棵树分成k个联通块，使得每个标记点独在一个联通块的最小删边代价
考虑并查集
虽然不能删边，但是可以逆向加边
跑最大生成树，如果当前边连接的两个城市不都是enemy，就加边，并让并查集合并
注：若两个集合的代表元素有一个是enemy，那么新集合的代表也是enemy
也就是说，当前集合有一个enemy，就把整个集合标记为enemy，这样就可以了
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> #include<cmath> using namespace std; #define olinr return #define _ 0 #define love_nmr 0 #define int long long #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int k; bool vis[105000]; struct node { int x; int y; int dis; friend bool operator < (const node &a,const node &b) { return a.dis>b.dis; } }edge[105000]; int fa[105000]; int tot; int ans; inline int findset(int x) { return x==fa[x]? fa[x]:fa[x]=findset(fa[x]); } double eps=1e-5; signed main() { n=read(); k=read(); for(int i=1;i<=k;i++) vis[read()]=true; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n-1;i++) { edge[i].x=read(); edge[i].y=read(); edge[i].dis=read(); tot+=edge[i].dis; } sort(edge+1,edge+n); for(int i=1;i<=n-1;i++) { int xx=findset(edge[i].x); int yy=findset(edge[i].y); if(!(vis[xx]&&vis[yy])) { fa[xx]=yy; if(vis[xx]||vis[yy]) vis[xx]=vis[yy]=true; tot-=edge[i].dis; } } put(tot); olinr ~~(0^_^0)+love_nmr; }