【题意】：给出一棵树，每条边都有一个价值，现在某k个点有炸弹，要你切断某些边，使得任意两个炸弹不连通。
【题解】：这题可以用树dp去解，但是有一种更巧妙的解法。
删边问题可以转换为求最大生成森林，把边按大到小排序，然后把所有炸弹结点指向同一集合。枚举边，用并查集去判断添加这条边是否会导致两个炸弹连通。
其实只是一个Kruskal算法的应用，不过转换确实巧妙。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 100050
26 int fa[maxn], tot;
27 int n, k;
28 struct Edge {
29 int u, v;
30 ll w;
31 Edge(){};
32 Edge(int _u, int _v, ll _w) {
33 u = _u, v = _v, w = _w;
34 }
35 bool operator<(const Edge &x) const {
36 return w > x.w;
37 }
38 }et[maxn];
39
40 void init() {
41 for(int i = 0; i < maxn; i++) fa[i] = i;
42 }
43
44 int find(int x) {
45 return (x == fa[x]) ? x : fa[x] = find(fa[x]);
46 }
47
48 bool Union(int a, int b) {
49 a = find(a), b = find(b);
50 if(a == b) return false;
51 else {
52 fa[a] = b;
53 return true;
54 }
55 }
56
57 int main() {
58 int T;
59 scanf("%d", &T);
60 while(T--) {
61 scanf("%d%d", &n, &k);
62 init();
63 tot = 0;
64 for(int i = 1; i < n; i++) {
65 int u, v;
66 ll w;
67 scanf("%d%d%I64d", &u, &v, &w);
68 et[tot++] = Edge(u, v, w);
69 }
70 for(int i = 0; i < k; i++) {
71 int a;
72 scanf("%d", &a);
73 fa[a] = n;
74 }
75 sort(et, et + tot);
76 ll ans = 0;
77 for(int i = 0; i < tot; i++) {
78 if(!Union(et[i].u, et[i].v)) ans += et[i].w;
79 }
80 cout << ans << endl;
81 }
82 return 0;
83 }
84