\(\color{#0066ff}{ 题目描述 }\)
在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。
\(\color{#0066ff}{输入格式}\)
第一行一个整数n，代表岛屿数量。
接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。
第n+1行，一个整数m，代表敌方机器能使用的次数。
接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。
\(\color{#0066ff}{输出格式}\)
输出有m行，分别代表每次任务的最小代价。
\(\color{#0066ff}{输入样例}\)
101 5 131 9 62 1 192 4 82 3 915 6 87 5 47 8 3110 7 932 10 64 5 7 8 33 9 4 6
\(\color{#0066ff}{输出样例}\)
123222
\(\color{#0066ff}{数据范围与提示}\)
对于10%的数据，2<=n<=10,1<=m<=5,1<=ki<=n-1
对于20%的数据，2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1)
对于40%的数据，2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1)
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
\(\color{#0066ff}{ 题解 }\)
对于每个询问，对关键点建立虚树
值得注意的是，我们的目的是不让它们与1相连， 而不是与虚树的根相连
所以1也要在虚树中
建好虚树，开始DP（因为要删的边权最小，所以建虚树的边是原树是上最小的边， 用倍增）
设f[i]为在虚树中，让以i为根的子树的关键点到不了i的最小代价
如果当前点是关键点，那么在它的子树中割边很显然是没意义的，所以直接返回\(dp[i] = inf\)
否则\(f[u] = \sum{min(f[v], dis_{u,v})}\)
最后再1处收集ans即可
#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}struct node { int to; LL dis; node *nxt; node(int to = 0, LL dis = 0, node *nxt = NULL): to(to), dis(dis), nxt(nxt) {} void *operator new (size_t) { static node *S = NULL, *T = NULL; return (S == T) && (T = (S = new node[1024]) + 1024), S++; }};const int maxn = 2e5 + 6e4;const LL inf = 999999999999999LL;node *head[maxn], *h[maxn];int dep[maxn], f[maxn][28], a[maxn], st[maxn], top, g[maxn], dfn[maxn];LL d[maxn][28], dp[maxn];int n, m, cnt;bool is[maxn];void add(int from, int to, LL dis, node **hh) { hh[from] = new node(to, dis, hh[from]);}void dfs(int x, int fa) { dfn[x] = ++cnt; f[x][0] = fa; dep[x] = dep[fa] + 1; for(node *i = h[x]; i; i = i->nxt) if(i->to != fa) dfs(i->to, x), d[i->to][0] = i->dis;}void LCA(int x, int y, LL &dis, int &id) { id = 0; dis = inf; if(dep[x] < dep[y]) std::swap(x, y); for(int i = 26; i >= 0; i--) if(dep[f[x][i]] >= dep[y]) dis = std::min(dis, d[x][i]), x = f[x][i]; if(x == y) return (void)(id = x); for(int i = 26; i >= 0; i--) if(f[x][i] != f[y][i]) dis = std::min(dis, std::min(d[x][i], d[y][i])), x = f[x][i], y = f[y][i]; dis = std::min(dis, std::min(d[x][0], d[y][0])); id = f[x][0];}void DP(int x) { if(is[x]) return (void)(dp[x] = inf); dp[x] = 0; for(node *i = head[x]; i; i = i->nxt) DP(i->to), dp[x] += std::min(dp[i->to], i->dis);}void clr(int x) { for(node *i = head[x]; i; i = i->nxt) clr(i->to); head[x] = NULL;}int main() { n = in(); int x, y, z; for(int i = 1; i < n; i++) { x = in(), y = in(), z = in(); add(x, y, z, h), add(y, x, z, h); } memset(d, 0x7f, sizeof d); dfs(1, 0); for(int j = 1; j <= 26; j++) for(int i = 1; i <= n; i++) { f[i][j] = f[f[i][j - 1]][j - 1]; d[i][j] = std::min(d[i][j - 1], d[f[i][j - 1]][j - 1]); } for(m = in(); m --> 0;) { int num = in(); for(int i = 1; i <= num; i++) a[i] = in(), is[a[i]] = true; a[++num] = 1; cnt = 0; std::sort(a + 1, a + num + 1, [](const int &x, const int &y) { return dfn[x] < dfn[y]; }); st[top = 1] = a[1]; LL D; int lca, id; for(int i = 2; i <= num; i++) { int now = a[i]; LCA(now, st[top], D, lca); while(top > 1 && dep[lca] <= dep[st[top - 1]]) { LCA(st[top], st[top - 1], D, id); add(st[top - 1], st[top], D, head); top--; } if(lca != st[top]) { LCA(st[top], lca, D, id); add(lca, st[top], D, head); st[top] = lca; } st[++top] = now; } while(top > 1) { LCA(st[top], st[top - 1], D, id); add(st[top - 1], st[top], D, head); top--; } DP(st[1]); printf("%lld\n", dp[st[1]]); clr(st[1]); for(int i = 1; i <= num; i++) is[a[i]] = false; } return 0;}