题目描述 link
在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。
输入格式
第一行一个整数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，表示资源丰富岛屿的编号。
输出格式
输出有m行，分别代表每次任务的最小代价。
输入输出样例
输入 #1
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
输出 #1
12
32
22
说明/提示
【数据规模和约定】
对于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
这题也是个虚树模板和CF613D Kingdom and its Cities 类似，我的题解link
建出虚树之后 ， 每个点要么弄他 ， 要么把他的儿子全弄了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
const int N = 251000;
#define int long long
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
#define RQ { puts("RQ"); /*exit(0);*/ }
int n , cnt , id , top , ans;
int head[N] , dfn[N] , a[N] , f[N][18] , sta[N] , d[N] , siz[N] , val[N] , dp[N];
vector<int> ed[N];
struct edge{int v , nex , c; } e[N<<1];
inline void add(int u , int v , int c) { e[++cnt].v = v; e[cnt].nex = head[u]; e[cnt].c = c; head[u] = cnt; return ;}
inline bool cmp(const int &A , const int &B) { return dfn[A] < dfn[B]; }
inline void addc(int u , int v) { ed[v].push_back(u); return ; }
void dfs(int x , int fa)
{
dfn[x] = ++id; d[x] = d[fa] + 1;
for(int i = 1 ; i <= 17 ; ++i) f[x][i] = f[f[x][i-1]][i-1];
for(int i = head[x] , v ; i ; i = e[i].nex)
{
v = e[i].v; if(v == fa) continue;
dp[v] = min(dp[x] , e[i].c);
f[v][0] = x; dfs(v , x);
}
return ;
}
int LCA(int x , int y)
{
if(x == y) return x;
int i; if(d[x] < d[y]) swap(x , y);
for(i = 17 ; i >= 0 ; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
for(i = 17 ; i >= 0 ; --i) if(f[x][i] ^ f[y][i]) x = f[x][i] , y = f[y][i];
return f[x][0];
}
void build_tree(int k)
{
sort(a + 1 , a + 1 + k , cmp);
top = 0; int i = 1;
if(a[1] != 1) sta[top = 1] = 1;
for(i = 1 ; i <= k ; ++i)
{
if(top <= 1) { sta[++top] = a[i]; continue; }
int p = LCA(sta[top] , a[i]);
if(p == sta[top]) continue;
while(top > 1 && d[sta[top-1]] >= d[p]) addc(sta[top] , sta[top-1]) , top--;
if(sta[top] != p) addc(sta[top] , p) , sta[top] = p;
sta[++top] = a[i];
}
while(top > 1) addc(sta[top] , sta[top-1]) , top--;
return ;
}
int dfs2(int x)
{
if((int)ed[x].size() == 0) return dp[x];
int res = 0;
for(int i = 0 , s = ed[x].size(); i < s ; ++i)
res += dfs2(ed[x][i]);
ed[x].clear();
return min(dp[x] , res);
}
signed main()
{
n = read();
for(int i = 1 , a , b , c; i < n ; ++i)
{
a = read() , b = read(); c = read();
add(a , b , c); add(b , a , c);
}
memset(dp , 0x3f , sizeof dp); dfs(1 , 0);
int m = read();
for(int i = 1 , k ; i <= m ; ++i)
{
k = read();
for(int j = 1 ; j <= k ; ++j) a[j] = read();
build_tree(k);
printf("%lld
" , dfs2(1));
}
return 0;
}
/*
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
*/