【题解】LOJ#2206 [HNOI2014]世界树

感觉是比较有难度的虚树题了。

倍增是用不会了,这辈子都用不会了。

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

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

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

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

对于所有的数据 $N\leq 300000, q\leq 300000, m_1+m_2+\ldots+m_q \leq 300000$。

这题大概就是难在不能很好地维护非关键点与关键点之间的关系。但是思路还是比较直观清晰的。考虑先求出虚树上所有点对纯虚点的贡献,然后考虑不在虚树上的点必然是以两个虚树上点之间的链的形式存在。那么就可以倍增出这个分界线来,之所以选用倍增而不是二分的原因显然:不用重复累加信息。

然后具体过程就是先 up_down 出虚树上点之间的信息,然后再 solve 一遍,对于虚树上每条边去倍增出分界线。然后这个地方存在细节:

0、倍增的时候可以考虑去倍增从两个点延伸出的范围。

1、不要忘了编号的约束,最后判一下就好了。

2、大概就是说如果用 size 去算链之间的点的分配势必会算多,但是也有个好处就是可以直接拿子树 size 去容斥,这样就可以一并算出那些 $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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <cctype>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

using std :: max ;

using std :: min ;

using std :: pair ;

using std :: swap ;

using std :: vector ;

using std :: make_pair ;

#define fr first
#define sc second
#define m_k make_pair
#define p_b push_back

const int N = 300005 ;

const int I = 1000000000 ;

typedef long long ll ;

int qr(){
int r = 0, f = 1 ;
char c = getchar() ;
while (c > '9' || c < '0'){
if (c == '-') f = -1 ; c = getchar() ;
}
while (c <= '9' && c >= '0'){
r = (r << 1) + (r << 3) + c - '0', c = getchar() ;
}
return r * f ;
}

int rt ;
int n, q, k ;
int base[N] ;
vector <int> E[N] ;

namespace virtual_tree{
int cnt ;
int sum ;
int sz[N] ;
int fa[N] ;
int nfa[N] ;
int dep[N] ;
int dfn[N] ;
int son[N] ;
int top[N] ;
int anc[N][19] ;
int stk[N], tp ;
vector <int> a ;
vector < pair<int, int> > T[N] ;
void dfs1(int x, int da){
anc[x][0] = da ;
dep[x] = dep[da] + 1 ;
sz[x] = 1, fa[x] = da ;
for (int i = 1 ; i <= 18 ; ++ i)
anc[x][i] = anc[anc[x][i - 1]][i - 1] ;
for (auto y : E[x]){
if (y == da) continue ;
dfs1(y, x) ; sz[x] += sz[y] ;
if (sz[y] > sz[son[x]]) son[x] = y ;
}
}
void dfs2(int x, int tp){
top[x] = tp ;
dfn[x] = ++ cnt ;
if (son[x])
dfs2(son[x], tp) ;
for (auto y : E[x])
if (y != fa[x] && y != son[x]) dfs2(y, y) ;
}
int lca(int x, int y){
if (!y) return 0 ;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]])
std :: swap(x, y) ; x = fa[top[x]] ;
}
if (dep[x] > dep[y])
std :: swap(x, y) ; return x ;
}
int dis(int a, int b){
if (!b) return 0 ;
return dep[a] + dep[b] - (dep[lca(a, b)] << 1) ;
}
void add_e(int x, int y){
// printf("%d %d\n", x, y) ;
if (x == y) return ; nfa[x] = y ;
T[y].p_b(m_k(x, dis(x, y))) ;
}
void ins(){
stk[0] = 1 ;
sort(a.begin(), a.end(), [](int x, int y){ return dfn[x] < dfn[y] ; }) ;
for (auto x : a){
int z = lca(x, stk[tp]) ;
if (z != stk[tp]){
while (tp && dep[stk[tp - 1]] >= dep[z])
add_e(stk[tp], stk[tp - 1]), -- tp ;
if (stk[tp] != z) add_e(stk[tp], z), stk[tp] = z ;
}
stk[++ tp] = x ;
}
while (tp)
add_e(stk[tp], stk[tp - 1]), -- tp ;
}
}

int ans[N] ;
int vis[N] ;
int minf[N] ;
int mind[N] ;

using namespace virtual_tree ;


void clear(int x){
for (auto y : T[x]) clear(y.fr) ;
T[x].clear(), ans[x] = vis[x] = mind[x] = 0, minf[x] = I ;
}
void do_up(int x){
// printf("%d\n", x) ;
if (vis[x]){
minf[x] = 0 ;
mind[x] = x ;
}
int y, z ;
for (auto t : T[x]){
y = t.fr ;
do_up(y) ;
z = minf[y] + dis(x, y) ;
if (z < minf[x])
minf[x] = z, mind[x] = mind[y] ;
else if (z == minf[x] && mind[x] > mind[y])
mind[x] = mind[y] ;
}
}
void do_down(int x, int v){
int y, z ;
if (nfa[x]){
y = nfa[x] ;
z = minf[y] + v ;
if (z < minf[x])
minf[x] = z, mind[x] = mind[y] ;
else if (z == minf[x] && mind[x] > mind[y])
mind[x] = mind[y] ;
}
// printf("%d %d %d\n", x, mind[x], minf[x]) ;
ans[mind[x]] ++ ;
for (auto t : T[x])
do_down(t.fr, t.sc) ;
}
int ancdis(int x, int y){
return dep[x] - dep[y] ;
}
pair <int, int> do_find(int x, int y){
bool ct = 0 ;
if (dep[x] < dep[y])
swap(x, y), ct = 1 ;
int dist = minf[x], z = x, nd = mind[x] ;
for (int i = 18 ; i >= 0 ; -- i)
if (dist + (1 << (i + 1)) < minf[y] + ancdis(x, y))
mind[x = anc[x][i]] = nd, dist += (1 << i) ;
if (dist + 2 == minf[y] + ancdis(x, y) && nd < mind[y]) x = fa[x] ;
// printf("$ %d %d %d %d %d %d\n", y, x, z, sz[y], sz[x], sz[z]) ;
if (ct)
return m_k(sz[y] - sz[x], sz[x] - sz[z]) ;
else return m_k(sz[x] - sz[z], sz[y] - sz[x]) ;
}
void solve(int x){
int y, z = sz[x] ;
// printf("#%d %d\n", x, z) ;
pair <int, int> res ;
for (auto t : T[x]){
y = t.fr ;
res = do_find(x, y) ;
//if (!x) goto cccccc ;
ans[mind[x]] += res.fr ;
ans[mind[y]] += res.sc ;
// printf("* %d %d\n", res.fr, res.sc) ;
z -= (res.fr + res.sc + sz[y]) ;
solve(y) ;
}
ans[mind[x]] += z - 1 ;
// printf("#%d %d\n", x, z) ;
}
int main(){
scanf("%d", &n) ; int x, y ;
memset(minf, 63, sizeof(minf)) ;
for (int i = 1 ; i < n ; ++ i)
x = qr(), y = qr(), E[x].p_b(y), E[y].p_b(x) ;
dfs1(rt = 1, 0), dfs2(rt, rt) ; q = qr() ;
while (q --){
k = qr() ; a.clear() ;
for (int i = 1 ; i <= k ; ++ i)
vis[base[i] = qr()] = 1, a.p_b(base[i]) ;
ins() ; do_up(1) ; do_down(1, 0) ;
solve(1) ;
for (int i = 1 ; i <= k ; ++ i)
printf("%d%c", ans[base[i]], " \n"[i == k]) ; clear(1) ;
}
return 0 ;
}