[WC2014] 紫荆花之恋 - 带权树上的朋友对数统计

[WC2014] 紫荆花之恋/n/n强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。/n/n仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 'i' 都有一个感受能力值 'r_i'，小精灵 'i,j' 成为朋友当且仅当在树上 'i' 和 'j' 的距离 'dist(i,j)' ≤ 'r_i + r_j'，其中 'dist(i,j)' 表示在这个树上从 'i' 到 'j' 的唯一路径上所有边的边权和。/n/n强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。/n/n/n我们假定这个树一开始为空，节点按照加入的顺序从 1 开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。/n/n## 输入格式/n/n第一行包含一个整数，表示测试点编号。/n/n第二行包含一个正整数 'n'，表示总共要加入的节点数。/n/n我们令加入节点前的总共朋友对数是 'last/_ans'，在一开始时它的值为 0。/n/n接下来 'n' 行中第 'i' 行有三个非负整数 'a_i,c_i,r_i'，表示结点 'i' 的父节点的编号为 'a_i ⊕ (last_ans mod 10^9)'（其中 '⊕' 表示异或，数据保证这样操作后得到的结果介于 1 到 'i−1' 之间），与父结点之间的边权为 'c_i'，节点 'i' 上小精灵的感受能力值为 'r_i'。/n/n注意 'a_1=c_1=0'，表示 1 号节点是根结点，对于 'i>1'，父节点的编号至少为 1。/n/n## 输出格式/n/n包含 'n' 行，每行输出 1 个整数，表示加入第 'i' 个点之后，树上有几对 friends。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n0/n5/n0 0 6/n1 2 4/n0 9 4/n0 5 5/n0 2 4/n/n/n### 样例输出 #1/n/n/n0/n1/n2/n4/n7/n/n/n## 提示/n/n所有数据均满足 '1 ≤ c_i ≤ 10^4'，'a_i ≤ 2×10^9'，'r_i ≤ 10^9'。/n/n| 测试点编号 | 约定 | /n| :----------------: | :------------------------------------------------------------: | /n| $1,2$ | $n ≤ 100$ | /n| $3,4$ | $n ≤ 1000$ | /n| $5,6,7,8$ | $n ≤ 10^5$，节点 1 最多有两个子节点，其他节点最多有一个子节点 | /n| $9,10$ | $n ≤ 10^5$，$r_i ≤ 10$ | /n| $11,12$ | $n ≤ 10^5$，树是随机生成的 | /n| $13,14,15$ | $n ≤ 7×10^4$ | /n| $16,17,18,19,20$ | $n ≤ 10^5$ | /n/n解题思路/n/n这个问题可以使用树状数组（Binary Indexed Tree）来解决。/n/n首先，我们需要定义一些变量。我们使用一个数组 'tree' 来表示树状数组，其中 'tree[i]' 存储的是以节点 'i' 为根节点的子树中的朋友对数。我们还使用一个数组 'friends' 来存储每个节点的感受能力值。/n/n接下来，我们需要实现一些函数。首先是 'add' 函数，用于将节点 'i' 的感受能力值加入到树状数组中。我们从节点 'i' 开始，一直向上更新树状数组中的值，直到达到根节点。更新的方法是将节点 'i' 的感受能力值加到 'tree[i]' 上，并将 'i' 的父节点的索引加到 'i' 上，即 'i += i & -i'。这样，我们就可以将节点 'i' 的感受能力值加到树状数组中了。/n/n接下来是 'query' 函数，用于计算节点 'i' 的朋友对数。我们从节点 'i' 开始，一直向上计算树状数组中的值，直到达到根节点。计算的方法是将节点 'i' 的感受能力值加到 'result' 上，并将 'i' 的父节点的索引减去 'i'，即 'i -= i & -i'。这样，我们就可以计算出节点 'i' 的朋友对数了。/n/n最后，我们使用一个循环来处理每个节点的输入。在每次循环中，我们先读取节点的信息，并将其感受能力值加入到树状数组中。然后，我们使用 'query' 函数计算出当前树状数组中的朋友对数，并将其输出。/n/n时间复杂度分析/n/n对于每个节点，我们需要执行 'add' 和 'query' 函数，每个函数的时间复杂度都是 O(log n)。因此，总的时间复杂度是 O(n log n)，其中 'n' 是节点的数量。/n/n空间复杂度分析/n/n除了输入和输出的空间外，我们只需要使用常数大小的额外空间。因此，空间复杂度是 O(1)。/n