Dynamic Fairy Friendship in a Growing Weighted Tree

In this problem, a growing weighted tree is introduced. The tree starts empty, and nodes are added one by one. When a node is added, it is attached as a new leaf node to an existing node. Each node i comes with a cute little fairy having a perception value r_i.

For any two nodes i and j in the tree, define dist(i, j) as the sum of edge weights on the unique path between them. Two fairies become friends if and only if \[ dist(i,j) \leq r_i + r_j \] After every new node is added, your task is to output the total number of friendly pairs in the current tree.

The tree grows as follows: the first node (node 1) appears with its fairy value. For each subsequent node (node i for i \geq 2), you are given three integers: the index of its parent p (which is an existing node), the weight w of the edge connecting it to p, and the fairy's perception value r for this new node.

You must output the cumulative friend pair count immediately after each addition. Note that a single node does not form a pair, so the friend count for just the root is 0.

inputFormat

The input begins with an integer n (n \ge 1) representing the total number of nodes added to the tree.

The next line contains an integer r, the fairy's perception value for node 1.

Then for each node i (from 2 to n), there is a line containing three space‐separated integers:

• p: the index of its parent node.
• w: the weight of the edge from node i to node p.
• r: the fairy's perception value for node i.

outputFormat

Output n lines. The i-th line (1-indexed) should contain the total number of friendly pairs among the first i nodes in the tree.

sample

4
10
1 5 5
1 3 2
2 2 1

0
1
2
4