#1306. 「WC2014」紫荆花之恋

内存限制:512 MiB 时间限制:12000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: panda_2134

题目描述

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

样例

样例输入

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

样例输出

0
1
2
4
7

数据范围与提示

对于所有数据,满足 1 \leq c_i \leq 10000 a_i≤2 \times 10^9 r_i≤10^9

测试点编号 约定
1, 2 n \leq 100
3, 4 n \leq 1000
5, 6, 7, 8 n \leq 100000 ,节点 11 最多有两个子节点,其它节点最多有一个子节点
9, 10 n≤100000 r_i \leq 10
11, 12 n \leq 100000 ,这棵树是随机生成的
13, 14, 15 n \leq 70000
16, 17, 18, 19, 20 n \leq 100000