题目描述

在一场战争中，战场由 nn 个岛屿和 n−1n-1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 11 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 kk 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 11 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 mm 次，所以我们只需要把每次任务完成即可。

输入格式

第一行一个整数 nn，表示岛屿数量。
接下来 n−1n-1 行，每行三个整数 u,v,wu,v,w，表示 uu 号岛屿和 vv 号岛屿由一条代价为 ww 的桥梁直接相连。
第 n+1n+1 行，一个整数 mm，代表敌方机器能使用的次数。
接下来 mm 行，第 ii 行一个整数 kik_i，代表第 ii 次后，有 kik_i 个岛屿资源丰富。接下来 kik_i 个整数 h1,h2,...,hkih_1,h_2,..., h_{k_i}，表示资源丰富岛屿的编号。

输出格式

输出共 mm 行，表示每次任务的最小代价。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
12
32
22

说明/提示

数据规模与约定。
对于 10%10\% 的数据，n⩽10,m⩽5n\leqslant 10, m\leqslant 5。
对于 20%20\% 的数据，n⩽100,m⩽100,1⩽ki⩽10n\leqslant 100, m\leqslant 100, 1\leqslant k_i\leqslant 10。
对于 40%40\% 的数据，n⩽1000,1⩽ki⩽15n\leqslant 1000, 1\leqslant k_i\leqslant 15。
对于 100%100\% 的数据，$2\leqslant n \leqslant 2.5\times 10^5, 1\leqslant m\leqslant 5\times 10^5, \sum k_i \leqslant 5\times 10^5, 1\leqslant k_i< n, h_i\neq 1, $$1\leqslant u,v\leqslant n, 1\leqslant w\leqslant 10^5$。

分析

称 kk 个资源丰富的点为关键点。定义 bookxbook_x，若 bookxbook_x 为真，xx 为关键点。定义 fxf_x，表示使 xx 不与其子树中任意一个关键点连通的最小代价。枚举 xx 的儿子 yy，有状态转移如下，式中的 MinimumCostxMinimumCost_x 表示使 xx 与根节点不连通的最小代价，即为 11 到 xx 路径上的最小边权。

fx={min⁡(∑fy,MinimumCostx)bookx=0MinimumCostxbookx=1f_x=\begin{cases}\min(\sum f_y,MinimumCost_x)&book_x=0\\MinimumCost_x&book_x=1\end{cases}

进行 mm 次询问，每次执行一遍上述的树形DP，时间复杂度为 O(mn)O(mn)，显然会 TLE\text{TLE}。注意到 ∑i=1mki⩽5×105\sum\limits_{i=1}^mk_i\leqslant 5\times10^5，不妨每次询问时将 kik_i 个点作为关键点建立虚树，在虚树上进行树形DP，时间复杂度为 O(∑ki)O(\sum k_i)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=250006;
const short magnitude=20;
struct E
{
	int to;
	ll cost;
	int Next;
};
int timer;
int tot,head[N];
int dfn[N];
int n,m;
int depth[N];//记录节点深度
int bin[N][22];//记录倍增祖先
E T[N<<1],VT[N<<1];
int Vtot,Vhead[N];
int h[N];
int s[N],top;
ll MinimumCost[N];
bool booked[N];
void init();
inline void add_edge(int,int);
inline void add_edge(int,int,int);
void BFS(int);
void DFS(int);
int LCA(int,int);
void insert(int);
ll f(int);
int main(){
	init();
	int i;
	cin>>n;
	for(i=1;i<=n-1;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	BFS(1);//倍增预处理
	DFS(1);//预处理DFS序
	cin>>m;
	while(m--){
		int k;
		scanf("%d",&k);
		for(i=1;i<=k;i++){
			scanf("%d",&h[i]);
			booked[h[i]]=1;
		}
		//按照DFS序排序
		sort(h+1,h+1+k,[](int x,int y){return dfn[x]<dfn[y];});
		s[top=1]=1;//根节点入栈
		for(i=1;i<=k;i++){
			insert(h[i]);
		}
		for(i=1;i<top;i++){
			add_edge(s[i],s[i+1]);
		}
		printf("%lld\n",f(1));
		Vtot=0;
	}
	return 0;
}
ll f(int x){
	ll sum=0;
	for(register int i=Vhead[x];~i;i=VT[i].Next){
		//遍历儿子
		int y=VT[i].to;
		sum+=f(y);
	}
	//讨论x是否为关键点
	ll ans=booked[x]?MinimumCost[x]:min(MinimumCost[x],sum);
	//访问到的点要清空
	booked[x]=0;
	Vhead[x]=-1;
	return ans;
}
void insert(int x){
	int lca=LCA(x,s[top]);
	if(lca!=s[top]){
		while(top>1&&dfn[lca]<dfn[s[top-1]]){
			add_edge(s[top-1],s[top]);
			top--;
		}
		if(dfn[lca]>dfn[s[top-1]]){
			add_edge(lca,s[top]);
			s[top]=lca;
		}else{
			add_edge(lca,s[top--]);
		}
	}
	s[++top]=x;
}
inline void add_edge(int u,int v,int w){
	tot++;
	T[tot].to=v;
	T[tot].cost=w;
	T[tot].Next=head[u];
	head[u]=tot;
}
inline void add_edge(int u,int v){
	Vtot++;
	VT[Vtot].to=v;
	VT[Vtot].Next=Vhead[u];
	Vhead[u]=Vtot;
}
void DFS(int x){
	dfn[x]=++timer;
	for(register int i=head[x];~i;i=T[i].Next){
		int y=T[i].to;
		if(dfn[y]){
			continue;
		}
		DFS(y);
	}
}
void BFS(int root){
	queue<int>q;
	q.push(root);
	depth[root]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=T[i].Next){
			int y=T[i].to;
			if(depth[y]){
				continue;
			}
			MinimumCost[y]=min(MinimumCost[x],T[i].cost);
			depth[y]=depth[x]+1;
			bin[y][0]=x;
			for(register int j=1;j<=magnitude;j++){
				bin[y][j]=bin[bin[y][j-1]][j-1];
			}
			q.push(y);
		}
	}
}
int LCA(int x,int y){
	if(depth[x]<depth[y]){
		swap(x,y);
	}
	int i;
	for(i=magnitude;i>=0;i--){
		if(depth[bin[x][i]]>=depth[y]){
			x=bin[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(i=magnitude;i>=0;i--){
		if(bin[x][i]!=bin[y][i]){
			x=bin[x][i];
			y=bin[y][i];
		}
	}
	return bin[x][0];
}
void init(){
	memset(MinimumCost,0x3f,sizeof(MinimumCost));
	memset(Vhead,-1,sizeof(Vhead));
	memset(head,-1,sizeof(head));
}