「SDOI 2011」消耗战【虚树】

Time Limit: 20 Sec Memory Limit: 512 MB

Description

在一场战争中,战场由 nn 个岛屿和 n1n-1 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 11 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 kk 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。

侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布 (但可以保证的是,资源不会分布到 11 号岛屿上)。不过侦查部门还发现了这台机器只能够使用 mm 次,所以我们只需要把每次任务完成即可。

Input

第一行包含一个整数 nn,代表岛屿数量。

接下来 n1n-1 行,每行包含三个整数 u,v,cu, v, c,代表 uu 号岛屿和 vv 号岛屿由一条代价为 cc 的桥梁直接相连,保证 1u,vn1 \leqslant u, v \leqslant n1c1000001 \leqslant c \leqslant 100000

n+1n+1 行包含一个整数 mm,代表敌方机器能使用的次数。

接下来 mm 行,每行一个整数 kik_i,代表第 ii 次后,有 kik_i 个岛屿资源丰富,接下来 kk 个整数 h1,h2,,hkih_1, h_2, \cdots, h_{k_i},表示资源丰富岛屿的编号。

Output

输出 mm 行,分别代表每次任务的最小代价。

Sample Input

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

Sample Output

1
2
3
12
32
22

Constraints

2n250000,2 \leqslant n \leqslant 250000, m1,m \geqslant 1, ki500000,\sum k_i \leqslant 500000, 1kin11 \leqslant k_i \leq n-1

Solution

有时,我们可能处理到这样的一类问题。对于一棵树,每一次会从中选出部分点进行询问。如果对于每次询问,都遍历整棵树,复杂度较高。但是这类问题一般都有一个特征,即如果每次询问的点数为 kk,那么有 k\sum knn 同阶。

虚树便可以解决这类问题。注意到,对于每一次询问,对象只是树上的一部分点,而树上其他的点我们并不会用到。因此,可以新建一棵树,使得这棵树上只保留需要的节点,但它仍然具有完整的树结构。

我们将所需要的节点称为关键点,则虚树会保留所有的关键点,以及任意两个关键点的 LCA\text{LCA}。如下图所示,橙色节点为关键节点,紫色为 LCA\text{LCA},建立虚树如右图所示:

virtual-tree

可以证明,虚树的总结点数与关键点数同阶。在树上随意选出 kk 个点,那么这 kk 个点的 LCA\text{LCA} 总数不会超过 k1k - 1

首先给出如下结论:如果将所有的 kk 个关键点按照 DFS\text{DFS} 序排序,求出所有相邻两节点的 LCA\text{LCA} 并加入到集合 SS 中。那么对于 kk 个关键点中的任意两点,它们的 LCA\text{LCA} (记为 ww) 一定满足 wSw \in S。证明如下:

  • 若对于具有祖先关系的两个节点 u,v (depudepv)u, v\ (\text{dep}_u \leqslant \text{dep}_v),显然 LCA(u,v)=u\text{LCA}(u, v) = u。考虑 DFS\text{DFS} 序,发现 uu 与按照 DFS\text{DFS} 序排序后位于 uu 后面的一个点 (一定位于以 uu 为根的子树内) 的 LCA\text{LCA} 也为 uu
  • 若对于不具有祖先关系的两个节点 u,vu, v,设 LCA(u,v)=x\text{LCA}(u, v) = x。将以 xx 为根的子树中包含关键点的子树依次即为 T1,T2,T_1, T_2, \cdots。那么必然存在在子树 T1T_1DFS\text{DFS} 序最大的点和在子树 T2T_2DFS\text{DFS} 序最小的点,它们的 LCA\text{LCA}xx

考虑如何建边,显然在原树中具有祖先关系的点之间都会有连边。可以使用一个栈,每次考虑节点 ii 时,都会保证以当前栈顶元素为根的子树中包含点 ii,因此栈顶元素要么是 ii 与另一个点的 LCA\text{LCA},要么是离 ii 最近的关键点,因此这样建边一定合法。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 500010;
int n, q, g, dfn, id[maxn], tid[maxn], S[maxn], fa[maxn], top[maxn], sz[maxn], dep[maxn], son[maxn];
ll w[maxn];
bool in[maxn];
vector<int> G[maxn], cost[maxn], e[maxn];
bool comp(int x, int y) { return tid[x] < tid[y]; }

void dfs1(int v, int f, int d) {
sz[v] = 1, dep[v] = d, fa[v] = f;
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i]; if (u == f) continue;
w[u] = min(w[v], (ll)cost[v][i]);
dfs1(u, v, d + 1), sz[v] += sz[u];
if (sz[u] > sz[son[v]]) son[v] = u;
}
}

void dfs2(int v, int rt) {
tid[v] = ++dfn, top[v] = rt;
if (son[v]) dfs2(son[v], rt);
for (int i = 0; i < G[v].size(); i++) {
if (G[v][i] != fa[v] && G[v][i] != son[v]) {
dfs2(G[v][i], G[v][i]);
}
}
}

int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return u;
}

void build(int k) {
sort(id + 1, id + k + 1, comp);
g = k;
for (int i = 2; i <= k; i++) {
id[++g] = lca(id[i], id[i - 1]);
}
id[++g] = 1, sort(id + 1, id + g + 1, comp);
g = unique(id + 1, id + g + 1) - id;
for (int i = 1, c = 0; i <= g; i++) {
while (c && tid[S[c]] + sz[S[c]] <= tid[id[i]]) c--;
e[S[c]].push_back(id[i]), S[++c] = id[i];
}
}

ll dp(int v) {
ll ans = w[v], sum = 0;
if (in[v]) return ans;
for (int i = 0; i < e[v].size(); i++) {
sum += dp(e[v][i]);
}
return min(ans, sum);
}

int main() {
scanf("%d", &n);
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].push_back(v), cost[u].push_back(w);
G[v].push_back(u), cost[v].push_back(w);
}
w[1] = 1e12, dfs1(1, 0, 0), dfs2(1, 1);
scanf("%d", &q);
for (int i = 1, k; i <= q; i++) {
scanf("%d", &k);
for (int j = 1; j <= k; j++) {
scanf("%d", &id[j]), in[id[j]] = 1;
}
build(k), printf("%lld\n", dp(1));
for (int j = 1; j <= g; j++) {
e[id[j]].clear(), in[id[j]] = 0;
}
}
return 0;
}