「HNOI 2014」世界树【虚树】

Time Limit: 20 Sec Memory Limit: 512 MB

Description

世界树中有 nn 个种族,种族的编号分别从 11nn,分别生活在编号为 11nn 的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为 11。保证连接的方式会形成一棵树结构,定义两个聚居地之间的距离为连接他们的道路的长度。

出于对公平的考虑,第 ii 年,世界树的国王需要授权 mim_i 个种族的聚居地为临时议事处。对于某个种族 xx (xx 为种族的编号),如果距离该种族最近的临时议事处为 yy (yy 为议事处所在聚居地的编号),则种族 xx 将接受 yy 议事处的管辖 (如果有多个临时议事处到该聚居地的距离一样,则 yy 为其中编号最小的临时议事处)。

现在国王想知道,在 qq 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族 (议事处所在的聚居地也将接受该议事处管理)。请帮国王完成这个任务吧。

Input

第一行为一个正整数 nn,表示世界树中种族的个数。
接下来 n1n - 1 行,每行两个正整数 x,yx, y,表示 xx 聚居地与 yy 聚居地之间有一条长度为 11 的双向道路。
接下来一行为一个正整数 qq,表示国王询问的年数。
接下来 qq 块,每块两行:

  • ii 块的第一行为一个正整数 mim_i,表示第 ii 年授权的临时议事处的个数。
  • ii 块的第二行为 mim_i 个正整数 h1,h2,,hmih_1, h_2, \cdots, h_{m_i},表示第 ii 年被授权为临时议事处的聚居地编号 (保证互不相同)。

Output

输出包含 qq 行,第 ii 行为 mim_i 个整数,该行的第 jj (j=1,2,,mi)(j = 1, 2, \cdots, m_i) 个数表示第 ii 年被授权的聚居地 hjh_j 的临时议事处管理的种族个数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8

Sample Output

1
2
3
4
5
1 9   
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1

Constraints

1n,q300000,1 \leqslant n, q \leqslant 300000, mi300000\sum m_i \leqslant 300000

Solution

注意到对询问点总数的限制,所以可以使用虚树。考虑如何 DP\text{DP}

首先需要求出每个非关键点被哪个关键点管辖,所以要讨论每个节点与其父亲和儿子的关系。故使用两次 DP\text{DP},一次讨论与儿子的关系,一次讨论与父亲的关系。

然后再求出每个关键点管辖的虚树外的点有哪些,跑一遍树形 DP\text{DP} 即可。如果两个相邻节点被同一个节点管辖,那么直接加上路径上的点数。否则就需要把路径上的点分割,可以使用倍增算法求出。

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

typedef long long ll;
const int maxn = 600010, INF = 0x3f3f3f3f;
int n, q, g, dfn, k, id[maxn], r[maxn], tid[maxn], S[maxn], fa[maxn], f[maxn][20], sz[maxn], dep[maxn];
int mind[maxn], bel[maxn], pa[maxn], val[maxn], ans[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 from, int d) {
tid[v] = ++dfn, sz[v] = 1, dep[v] = d, f[v][0] = fa[v] = from;
for (int i = 1; (1 << i) < dep[v]; i++) {
f[v][i] = f[f[v][i - 1]][i - 1];
}
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i]; if (u == from) continue;
dfs1(u, v, d + 1), sz[v] += sz[u];
}
}

int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (dep[f[u][i]] >= dep[v]) {
u = f[u][i];
}
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (f[u][i] != f[v][i]) {
u = f[u][i], v = f[v][i];
}
}
return f[u][0];
}

int find(int x, int d) {
for (int i = 19; i >= 0; i--) {
if (f[x][i] >= 0 && dep[f[x][i]] >= d) {
x = f[x][i];
}
}
return x;
}

void build() {
sort(id + 1, id + k + 1, comp);
g = k;
for (int i = 2; i <= k; i++) {
id[++g] = lca(id[i], id[i - 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]), cost[S[c]].push_back(dep[id[i]] - dep[S[c]]), S[++c] = id[i];
}
}

void dfs2(int v) {
if (in[v]) mind[v] = 0, bel[v] = v;
for (int i = 0; i < e[v].size(); i++) {
int u = e[v][i];
pa[u] = v, dfs2(u);
if (mind[u] + cost[v][i] < mind[v] || (mind[u] + cost[v][i] == mind[v] && bel[u] < bel[v])) {
bel[v] = bel[u], mind[v] = mind[u] + cost[v][i];
}
}
}

void dfs3(int v, int from, int d) {
if (mind[from] + d < mind[v] || (mind[from] + d == mind[v] && bel[from] < bel[v])) {
bel[v] = bel[from], mind[v] = mind[from] + d;
}
for (int i = 0; i < e[v].size(); i++) {
dfs3(e[v][i], v, cost[v][i]);
}
}

void solve() {
for (int i = 1; i < g; i++) {
val[id[i]] = sz[id[i]], pa[id[i]] = ans[id[i]] = 0;
}
mind[0] = INF, dfs2(id[1]), dfs3(id[1], 0, 0);
ans[bel[id[1]]] += n - sz[id[1]];
for (int i = 2; i < g; i++) {
int v = id[i], p = pa[v], u = find(v, dep[p] + 1);
val[p] -= sz[u];
if (bel[v] == bel[p]) {
ans[bel[v]] += sz[u] - sz[v];
} else {
int gx = dep[v] - ((mind[p] + dep[v] - dep[p] - mind[v]) >> 1);
int ch = (gx - dep[p] + mind[p] == dep[v] - gx + mind[v] && bel[p] < bel[v]) ? find(v, gx + 1) : find(v, gx);
ans[bel[p]] += sz[u] - sz[ch], ans[bel[v]] += sz[ch] - sz[v];
}
}
for (int i = 1; i < g; i++) {
ans[bel[id[i]]] += val[id[i]];
}
for (int i = 1; i <= k; i++) {
printf("%d%c", ans[r[i]], " \n"[i == k]);
}
}

int main() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
memset(f, -1, sizeof(f)), fill(mind + 1, mind + n + 1, INF);
dfs1(1, 0, 1);
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d", &k);
for (int j = 1; j <= k; j++) {
scanf("%d", &id[j]), in[r[j] = id[j]] = 1;
}
build(), solve();
for (int j = 1; j < g; j++) {
e[id[j]].clear(), cost[id[j]].clear(), in[id[j]] = 0, mind[id[j]] = INF;
}
}
return 0;
}