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

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

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

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

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

【输入格式】

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

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

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

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

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

【输出格式】

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

【数据范围】

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

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

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

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

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

\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 记录下当前子树内的所有数。又因为要扣掉不合法的信息,再在这个节点记录下以它父亲(这里指的是分治结构中的父亲)为根,当前子树内的信息,这样走到它父亲的时候就可以用这个信息把不合法的减掉了

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

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

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/bzoj-3435

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.