BZOJ-3435. [Wc2014]紫荆花之恋

Posted by miskcoo on May 23, 2015

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 $i$ 都有一个感受能力值 $r_i$,小精灵 $i,j$ 成为朋友当且仅当在树上 $i$ 和 $j$ 的距离 $\text{dist}(i,j) \leq r_i+r_j$,其中 $\text{dist}(i,j)$ 表示在这个树上从 $i$ 到 $j$ 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。

我们假定这个树一开始为空,节点按照加入的顺序从 $1$ 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。

【输入格式】

第一行包含一个整数,表示测试点编号。

第二行包含一个正整数 $n$,表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 $\text{last_ans}$,在一开始时它的值为 $0$。

接下来 $n$ 行中第 $i$ 行有三个非负整数 $ai,ci,ri$,表示结点 $i$ 的父节点的编号为 $a_i \oplus (\text{last_ans} \bmod 10^9)$(其中 $\oplus$ 表示异或,$\text{mod}$ 表示取余,数据保证这样操作后得到的结果介于 $1$ 到 $i-1$ 之间),与父结点之间的边权为 $c_i$,节点 $i$ 上小精灵的感受能力值为 $r_i$。

注意 $a_1=c_1=0$,表示 $1$ 号节点是根结点,对于 $i>1$,父节点的编号至少为 $1$。

【输出格式】

包含 $n$ 行,每行输出 $1$ 个整数,表示加入第 $i$ 个点之后,树上有几对朋友。

【数据范围】

$n \leq 10^5$,$1 \leq c_i \leq 10^4$,$a_i \leq 2\times 10^9$,$r_i \leq 10^9$,时限 12s

这又是一道陈老师的可怕题目QAQ

首先我们来想想暴力要怎么写,和树分治类似的,考虑以 $u$ 为根的子树中,所有经过 $u$ 的路径,这样条件可以转化为

\[\text{dist}(a)+\text{dist}(b)\leq r_a+r_b\]

这里的 $\text{dist}(a)$ 表示 $a$ 到 $u$ 的距离,我们把变量归到一边

\[\text{dist}(a)-r_a\leq r_b-\text{dist}(b)\]

这样如果我们把 $u$ 子树内所有节点的 $\text{dist}(a) - r_a$ 记录下来,对于每个点 $b$,就是要查询比 $r_b - \text{dist}(b)$ 小的数有多少个,然后再扣掉来自相同子树的 $(a, b)$

这样的话再考虑加入一个点 $u$,那么 $u$ 到根路径上的所有点的子树所拥有的信息都会加上 $\text{dist}(u) - r_u$,并且要求查询的东西还是没有变,问题变成要支持加入一些数和查询小于某个值的数有多少个,所以我们用平衡树维护这个东西,然后不断往上走询问并且更新答案

但是有一个问题就是,如果碰到一条链的情况,每次都要从底走到顶,时间和空间都会变成平方级别以上。这时候可以借助替罪羊树的思想,当遇到某个节点过于不平衡,就暴力重构成平衡的东西,在这题中,最平衡的结构就是树分治的结构,因此,在重构的时候就用树分治来重构就可以了

关于实现的方法,由于要查询子树的信息,我们可以在替罪羊树的节点上用 Treap 记录下当前子树内的所有数。又因为要扣掉不合法的信息,再在这个节点记录下以它父亲(这里指的是分治结构中的父亲)为根,当前子树内的信息,这样走到它父亲的时候就可以用这个信息把不合法的减掉了

因为每次都是自底向上插入和查询,我们可以不必记录替罪羊树的儿子,只需记下父亲是谁。在重构的时候由于要遍历整棵子树、插入的时候需要知道两点间的路径长度,就需要单独保存这棵树的形态,而不是替罪羊树保存的奇怪的分治结构

另外,每个分治结构的重心和它父亲的重心不一定有直接连边,还要记录下这个分治结构中它父亲连向它的哪个节点,这样才可以在插入的时候维护刚刚所说的第二个信息,具体可以看看我的代码

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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <stack>

const int MaxL = 17, MaxN = 100010, MaxS = MaxN * 60;
const int inf = ~0u >> 1;
double alpha = 0.9;

struct graph_t
{
	int total;
	int head[MaxN], point[MaxN << 1];
	int next[MaxN << 1], weight[MaxN << 1];
	int fa[MaxL][MaxN], dist[MaxN], depth[MaxN];

	void add_edge(int u, int v, int w)
	{
		weight[++total] = w;
		point[total] = v;
		next[total] = head[u];
		head[u] = total;
	}

	void add_child(int u, int f, int w)
	{
		add_edge(u, f, w);
		add_edge(f, u, w);
		fa[0][u] = f;
		dist[u] = dist[f] + w;
		depth[u] = depth[f] + 1;

		for(int i = 1; i != MaxL; ++i)
			fa[i][u] = fa[i - 1][fa[i - 1][u]];
	}

	int get_lca(int u, int v)
	{
		if(depth[u] < depth[v]) 
			std::swap(u, v);
		int diff = depth[u] - depth[v];
		for(int i = 0; diff; ++i, diff >>= 1)
			if(diff & 1) u = fa[i][u];

		for(int p = MaxL - 1; u != v; p ? --p : 0)
		{
			if(!p || fa[p][u] != fa[p][v])
			{
				u = fa[p][u];
				v = fa[p][v];
			}
		}

		return v;
	}

	int get_dist(int u, int v)
	{
		int lca = get_lca(u, v);
		return dist[u] + dist[v] - (dist[lca] << 1);
	}
} gp;

struct treap_t
{
	int val, size;
	treap_t *l, *r;
} treap_node[MaxS];
int treap_used;
treap_t *treap_nil;
std::stack<treap_t*> treap_mem;

treap_t *treap_newnode()
{
	if(!treap_mem.empty())
	{
		treap_t *n = treap_mem.top();
		treap_mem.pop();
		if(n->l != treap_nil)
 			treap_mem.push(n->l);
		if(n->r != treap_nil)
			treap_mem.push(n->r);
		return n;
	} else return treap_node + treap_used++;
}

void treap_insert(treap_t*& n, int v)
{
	if(n == treap_nil)
	{
		n = treap_newnode();
		*n = *treap_nil;
		n->size = 1; n->val = v;
	} else {
		++n->size;
		if(v < n->val)
		{
			treap_insert(n->l, v);
			if(n->l->size > n->r->size + 3)
			{
				// left rotate
				treap_t *q = n->l;
				n->l = q->r; q->r = n;
				q->size = n->size;
				n->size = n->l->size + n->r->size + 1;
				n = q;
			}
		} else {
			treap_insert(n->r, v);
			if(n->r->size > n->l->size + 3)
			{
				// right rotate
				treap_t *q = n->r;
				n->r = q->l; q->l = n;
				q->size = n->size;
				n->size = n->l->size + n->r->size + 1;
				n = q;
			}
		}
	}
}

int treap_find(treap_t* n, int v)
{
	int ans = 0;
	while(n != treap_nil)
	{
		if(v < n->val)
		{
			n = n->l;
		} else {
			ans += n->l->size + 1;
			n = n->r;
		}
	}
	return ans;
}

struct scape_t
{
	int size, top;
	scape_t *fa;
	treap_t *info, *parent_info;
} scape_node[MaxN];
scape_t *scape_nil;
int node_num, R[MaxN], depth[MaxN];
int mark_v, mark[MaxN], que[MaxN], fa[MaxN];
int size[MaxN], max_size[MaxN], dist[MaxN];
int record_num, record[MaxN];
long long lastans;

int bfs_sort(int u)
{
	int qhead = 0, qtail = 0;
	que[qtail++] = u;
	fa[u] = 0;
	while(qhead != qtail)
	{
		int u = que[qhead++];
		size[u] = max_size[u] = 0;
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(mark[v] == mark_v && fa[u] != v)
			{
				fa[v] = u;
				que[qtail++] = v;
			}
		}
	}

	return qtail;
}

scape_t* divide(int r, scape_t *f, int dep)
{
	int tot = bfs_sort(r);
	for(int i = tot - 1; i >= 0; --i)
	{
		int u = que[i];
		size[u] += 1;
		size[fa[u]] += size[u];
		if(max_size[fa[u]] < size[u])
			max_size[fa[u]] = size[u];
	}

	int root, root_size = ~0u >> 1;
	for(int i = 0; i != tot; ++i)
	{
		int u = que[i];
		if(max_size[u] < size[r] - size[u])
			max_size[u] = size[r] - size[u];
		if(max_size[u] < root_size)
			root = u, root_size = max_size[u];
	}

	dist[r] = 0;
	for(int i = 0; i != tot; ++i)
	{
		int u = que[i];
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(fa[u] != v && mark[v] == mark_v)
				dist[v] = dist[u] + gp.weight[k];
		}
	}

	tot = bfs_sort(root);
	mark[root] = 0; depth[root] = dep;
	scape_t *n = scape_node + root;
	n->fa = f; n->top = r; n->size = tot;

	for(int i = 0; i != tot; ++i)
		treap_insert(n->parent_info, dist[que[i]] - R[que[i]]);
	treap_insert(n->info, -R[root]);

	for(int k = gp.head[root]; k; k = gp.next[k])
	{
		int v = gp.point[k];
		if(mark[v] == mark_v)
		{
			scape_t *son = divide(v, n, dep + 1);
			int qhead = 0, qtail = 0;
			que[qtail++] = son->parent_info - treap_node;
			while(qhead != qtail)
			{
				treap_t *z = treap_node + que[qhead++];
				treap_insert(n->info, z->val + gp.weight[k]);
				if(z->l != treap_nil)
					que[qtail++] = z->l - treap_node;
				if(z->r != treap_nil)
					que[qtail++] = z->r - treap_node;
			}
		}
	}

	return n;
}

void scape_rebuild(scape_t *n)
{
	int qhead = 0, qtail = 0;
	int id = n - scape_node;
	que[qtail++] = id;
	mark[id] = ++mark_v;
	while(qhead != qtail)
	{
		int u = que[qhead++];
		treap_mem.push(scape_node[u].info);
		treap_mem.push(scape_node[u].parent_info);
		scape_node[u].info = treap_nil;
		scape_node[u].parent_info = treap_nil;
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(depth[v] > depth[id] && mark[v] != mark_v)
				que[qtail++] = v, mark[v] = mark_v;
		}
	}

	int dep = depth[n - scape_node];
	divide(n->top, n->fa, dep);
}

void scape_insert(int n, int fa, int dist, int r)
{
	// set tree info
	R[n] = r;
	gp.add_child(n, fa, dist);

	// set split info
	depth[n] = depth[fa] + 1;

	// init node
	scape_t *z = scape_node + n;
	*z = *scape_nil;
	z->size = 1; z->top = n;
	z->fa = scape_node + fa;
	treap_insert(z->info, -r);
	treap_insert(z->parent_info, -r);

	scape_t *unbalanced_node;
	double unbalanced_val = 0.0;

	// update chain
	for(scape_t *prev = z, *now = z->fa; now != scape_nil; prev = now, now = now->fa)
	{
		++now->size;
		// balance size
		if(double(prev->size) / now->size > unbalanced_val)
		{
			unbalanced_node = now;
			unbalanced_val = double(prev->size) / now->size;
		}

		// calc answer
		int d = gp.get_dist(now - scape_node, n);
		treap_insert(now->info, d - r);

		int dz = gp.get_dist(now->top, n);
		treap_insert(now->parent_info, dz - r);

		int id = now - scape_node;
		lastans += treap_find(now->info, r - d);

		int dn = gp.get_dist(prev->top, now - scape_node);
		lastans -= treap_find(prev->parent_info, r - d - dn);
	}

	if(unbalanced_val > alpha)
		scape_rebuild(unbalanced_node);
}

void init()
{
	treap_nil = treap_node + treap_used++;
	treap_nil->l = treap_nil->r = treap_nil;
	treap_nil->size = 0;

	scape_nil = scape_node;
	scape_nil->fa = scape_nil;
	scape_nil->info = treap_nil;
	scape_nil->parent_info = treap_nil;
	scape_nil->size = 0;
}

int main()
{
	int n;
	std::scanf("%*d %d", &n);
	init();
	for(int i = 1; i <= n; ++i)
	{
		int a, b, r;
		std::scanf("%d %d %d", &a, &b, &r);
		a ^= lastans % 1000000000;
		scape_insert(i, a, b, r);
		std::printf("%lld\n", lastans);
	}
	return 0;
}