P3920 [WC2014] Love of the Bauhinia

Qiangqiang and Mengmeng are good friends. One day while strolling outside, they suddenly saw a bauhinia tree ahead. It was the season when bauhinia blossoms flutter, and countless petals were growing from the tree at a speed visible to the naked eye. Looking closely, this big tree is actually a weighted tree. At each moment it grows a new leaf node. There is a cute little spirit on every node, and a new spirit also appears on each newly grown node. Spirits are adorable but fragile creatures. Each spirit $i$ has a sensitivity value $r_i$. Spirits $i$ and $j$ become friends if and only if their distance on the tree satisfies $\operatorname{dist}(i,j) \leq r_i + r_j$, where $\operatorname{dist}(i,j)$ denotes the sum of edge weights along the unique path from $i$ to $j$ on this tree. Qiangqiang and Mengmeng are curious: after each new leaf node appears, how many pairs of friends are there in total on the tree? We assume the tree is initially empty, and nodes are numbered from $1$ in the order they are added. Since Qiangqiang is very curious, you must output the total number of friend pairs immediately after each new node appears, without delay.

The first line contains an integer representing the test point ID. The second line contains a positive integer $n$, the total number of nodes to be added. Let $last\_ans$ be the total number of friend pairs before adding the current node, with initial value $0$. In each of the next $n$ lines, the $i$-th line contains three non-negative integers $a_i, c_i, r_i$, meaning that the parent ID of node $i$ is $a_i \oplus (last\_ans \bmod 10^9)$ (where $\oplus$ denotes XOR; the data guarantees that the result after this operation lies between $1$ and $i-1$ inclusive), the edge weight to its parent is $c_i$, and the sensitivity of the spirit on node $i$ is $r_i$. Note that $a_1 = c_1 = 0$, meaning node $1$ is the root. For $i > 1$, the parent ID is at least $1$.

Output $n$ lines. The $i$-th line contains one integer: the number of pairs of friends in the tree after adding node $i$.

All data satisfy $1 \leq c_i \leq 10^4$, $a_i \leq 2 \times 10^9$, and $r_i \leq 10^9$. | Test point ID | Assumption | | :-----------: | :-----------------------------------------------------------: | | $1,2$ | $n \leq 100$ | | $3,4$ | $n \leq 1000$ | | $5,6,7,8$ | $n \leq 10^5$, node $1$ has at most two children, other nodes have at most one child | | $9,10$ | $n \leq 10^5$, $r_i \leq 10$ | | $11,12$ | $n \leq 10^5$, the tree is generated randomly | | $13,14,15$ | $n \leq 7 \times 10^4$ | | $16,17,18,19,20$ | $n \leq 10^5$ | Translated by ChatGPT 5