Problem Description
Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a
unique path between any pair of cities.
Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and
anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines. i.e after destroying those roads there should not be any path between any two Machines.
Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get destroyed and they
can be destroyed only one at a time.
You need to write a program that tells Neo the minimum amount of time he will require to disrupt the connection among machines.
Input
The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case the first line input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time.Then follow K lines each containing an integer. The ith integer is the id of city in which ith Machine is currently located.
2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000
Output
For each test case print the minimum time required to disrupt the connection among Machines.
Sample Input
1
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
Sample Output
10
題意：給你n個點n-1條邊，其中有k個頂點有機器人，為使得每個機器人都不連通，問你所需刪除的最小的權值和是多少？
思路：krusal的變形，按邊權從大到小排序，如果兩個城市不都有機器人則合並，並更新每個城市的機器人，否者刪除。
AC代碼：
[cpp]
#include<cstdio>
#include<string.h>
#include<algorithm>
#define N 100005
using 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;
}
