Matrix&&2012 Multi-University Training Contest 2
Problem DescriptionInputOutputSample InputSample Output#include<cstdio>#include<string.h>#include<algorithm>#define N 100005using namespace std;typedef struct node{int x;int y;int len;bool operator<(node a)const{return len>a.len;}}Node;Node s[N];int Father[N];bool flag[N];int n,m;void in(int &a){char ch;while((ch=getchar())<'0'||ch>'9');for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';}int Find(int x){if(x==Father[x]) return x;return Father[x]=Find(Father[x]);}void init(){in(n),in(m);for(int i=0;i<n;++i) Father[i]=i,flag[i]=false;for(int i=0;i<n-1;++i)in(s[i].x),in(s[i].y),in(s[i].len);sort(s,s+n-1);for(int i=0;i!=m;++i){int a;in(a);flag[a]=true;}}int main(){int T;in(T);while(T--){init();__int64 sum=0;for(int i=0;i!=n-1;++i){int x=Find(s[i].x);int y=Find(s[i].y);if(flag[x]&&flag[y]){sum+=s[i].len;continue;}if(flag[x]||flag[y]) flag[x]=flag[y]=true; Father[x]=y;}printf("%I64d\n",sum);}return 0;}
