P3920 [WC2014] 紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。 仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 $i$ 都有一个感受能力值 $r_i$，小精灵 $i,j$ 成为朋友当且仅当在树上 $i$ 和 $j$ 的距离 $dist(i,j) \leq r_i+r_j$，其中 $dist(i,j)$ 表示在这个树上从 $i$ 到 $j$ 的唯一路径上所有边的边权和。 强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。 我们假定这个树一开始为空，节点按照加入的顺序从 1 开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。

无

无

所有数据均满足 $1 \leq c_i \leq 10^4$，$a_i \leq 2\times 10^9$，$r_i \leq 10^9$。 | 测试点编号 | 约定 | | :----------------: | :------------------------------------------------------------: | | $1,2$ | $n \leq 100$ | | $3,4$ | $n \leq 1000$ | | $5,6,7,8$ | $n \leq 10^5$，节点 1 最多有两个子节点，其他节点最多有一个子节点 | | $9,10$ | $n \leq 10^5$，$r_i \leq 10$ | | $11,12$ | $n \leq 10^5$，树是随机生成的 | | $13,14,15$ | $n \leq 7\times 10^4$ | | $16,17,18,19,20$ | $n \leq 10^5$ |