#1270. [Wc2014] 紫荆花之恋
[Wc2014] 紫荆花之恋
题目背景
警告,滥用本题者将被封号。
题目描述
强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。
仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 都有一个感受能力值 ,小精灵 成为朋友当且仅当在树上 和 的距离 ,其中 表示在这个树上从 到 的唯一路径上所有边的边权和。
强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。
我们假定这个树一开始为空,节点按照加入的顺序从 1 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。
输入格式
第一行包含一个整数,表示测试点编号。
第二行包含一个正整数 ,表示总共要加入的节点数。
我们令加入节点前的总共朋友对数是 ,在一开始时它的值为 0。
接下来 行中第 行有三个非负整数 ,表示结点 i 的父节点的编号为 (其中 表示异或,数据保证这样操作后得到的结果介于 1 到 之间),与父结点之间的边权为 ,节点 上小精灵的感受能力值为 。
注意 ,表示 1 号节点是根结点,对于 ,父节点的编号至少为 1。
输出格式
包含 行,每行输出 1 个整数,表示加入第 个点之后,树上有几对 friends。
0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4
0
1
2
4
7
提示
所有数据均满足 ,,。
测试点编号 | 约定 |
---|---|
,节点 1 最多有两个子节点,其他节点最多有一个子节点 | |
, | |
,树是随机生成的 | |