「BZOJ3572」[Hnoi2014]世界树

Description

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。

世界树的形态可以用一个数学模型来描述:世界树中有 nn 个种族,种族的编号分别从 11nn,分别生活在编号为 11nn 的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为 11。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地 aabb 之间有道路,bbcc 之间有道路,因为每条道路长度为 11 而且又不可能出现环,所以 aacc 之间的距离为 22

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

现在国王想知道,在 qq 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数 nn,表示世界树中种族的个数。
接下来 n1n-1 行,每行两个正整数 xxyy,表示 xx 聚居地与 yy 聚居地之间有一条长度为 11 的双向道路。
接下来一行为一个正整数 qq,表示国王询问的年数。
接下来 qq 块,每块两行:
ii 块的第一行为一个正整数 mim_i,表示第 ii 年授权的临时议事处的个数。
ii 块的第二行为 mim_i 个正整数 h1,h2,,hmih_1, h_2, \ldots, h_{m_i},表示第 ii 年被授权为临时议事处的聚居地编号(保证互不相同)。

Output

输出包含 qq 行,第 ii 行为 mim_i 个整数,该行的第 j (j=1,2,,m[i])j\ (j=1,2,\ldots,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

HINT

对于所有的数据 N300000, q300000, m1+m2++mq300000N\leq 300000,\ q\leq 300000,\ m_1+m_2+\ldots+m_q \leq 300000

Solution

明确f、ans数组,

fxf_x 表示belxbel_x通过xx这个点能够控制的点的数量
起始值是sizxsizysiz_x - \sum siz_y yyxx在虚树上的直接儿子
然后遍历儿子边,找到分界点zzzz上面是由belxbel_x控制,下面到yy都是由belybel_y控制。
fx=val[midy]f_x -= val[mid\to y]
fy+=val[midy]f_y += val[mid\to y]
这是显然的。
最后ans[belx]+=f[x]ans[bel_x] += f[x]

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
171
172
173
174
175
176
177
178
179
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 500000;
int head[N], en;
struct Edge {
int u, v, nxt;
}e[N * 2];
int n, m, d[N];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int dfn[N], num, siz[N];
int f[N][21];
void dfs(int x, int F) {
dfn[x] = ++num;
d[x] = d[F] + 1;
f[x][0] = F;
siz[x] = 1;
for(int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
siz[x] += siz[y];
}
}
int lca(int x, int y) {
if(d[x] < d[y]) swap(x, y);
for(int i = 20; ~i; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
for(int i = 20; ~i; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int getdis(int x, int y) {
if(x == 0 || y == 0) return 1e9;
int z = lca(x, y);
return d[x] + d[y] - 2 * d[z];
}
int get(int x, int w) {
for(int i = 0; i <= 20; ++i) if(w & (1 << i)) x = f[x][i];
return x;
}
int t;
struct Que {
int x, i;
bool operator < (const Que &rhs) const {
return dfn[x] < dfn[rhs.x];
}
}a[N];
bool v[N];
struct GGG {
int head[N], en;
struct Edge {
int u, v, nxt;
}e[N * 2];
int n, m;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int top, st[N];
int f[N], ans[N], bel[N];
void init() {
st[top = 1] = 1;
for(int i = 1; i <= en; ++i) head[e[i].u] = 0;
for(int i = 1; i <= en; ++i) {
bel[e[i].u] = bel[e[i].v] = 0;
f[e[i].u] = f[e[i].v] = 0;
ans[e[i].u] = ans[e[i].v] = 0;
}
en = 0;
}
void ins(int x) {
int p = lca(st[top], x);
while(top > 1 && d[st[top - 1]] >= d[p]) addedge(st[top - 1], st[top]), --top;
if(st[top] == p) {
st[++top] = x;
return;
}
addedge(p, st[top]);
st[top] = p;
st[++top] = x;
}
void dfs(int x, int F) {
if(v[x]) bel[x] = x;
else bel[x] = bel[F];
f[x] = siz[x];
int val1, val2;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
dfs(y, x);
f[x] -= siz[y];
val1 = getdis(bel[y], x);
val2 = getdis(bel[x], x);
if(val1 < val2 || val1 == val2 && bel[y] < bel[x]) bel[x] = bel[y];
}
}
void dfs2(int x, int F) {
int val1 = getdis(x, bel[x]);
int val2 = getdis(x, bel[F]);
if(val1 > val2 || val1 == val2 && bel[F] < bel[x]) bel[x] = bel[F];
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
dfs2(y, x);
}
}

void solve(int x, int F) {
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;

int r = d[y] - d[x] + 1, l = 0;
while(r - l > 1) {
int mid = (l + r) >> 1;
int t = get(y, mid);
int val1 = getdis(t, bel[x]);
int val2 = getdis(t, bel[y]);
if(val1 > val2 || val1 == val2 && bel[x] > bel[y]) l = mid;
else r = mid;
}
int z = get(y, l);
f[x] -= siz[z] - siz[y];
f[y] += siz[z] - siz[y];
solve(y, x);
}
ans[bel[x]] += f[x];
}

}g;
int ans[N];
int main() {
n = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs(1, 1);
int Q = read();
d[0] = 1e7;
for(int T = 1; T <= Q; ++T) {
t = read();
for(int i = 1; i <= t; ++i)
a[i].x = read(), a[i].i = i;
sort(a + 1, a +1 + t);
g.init();
for(int i = 1; i <= t; ++i) v[a[i].x] = 1;
for(int i = (a[1].x == 1 ? 2 : 1); i <= t; ++i) g.ins(a[i].x);
while(g.top > 1) g.addedge(g.st[g.top - 1], g.st[g.top]), g.top--;

g.dfs(1, 0);
g.dfs2(1, 0);
g.solve(1, 0);

for(int i = 1; i <= t; ++i) {
ans[a[i].i] = g.ans[a[i].x];
}
for(int i = 1; i <= t; ++i) printf("%d ", ans[i]);
puts("");
for(int i = 1; i <= t; ++i) v[a[i].x] = 0;
}
return 0;
}