Path Prefixes
Contest: Codeforces Round 811 (Div. 3)
Difficulty rating: 1700
Tags: binary search, data structures, dfs and similar, trees

You are given a rooted tree. It contains $$$n$$$ vertices, which are numbered from $$$1$$$ to $$$n$$$. The root is the vertex $$$1$$$.

Each edge has two positive integer values. Thus, two positive integers $$$a_j$$$ and $$$b_j$$$ are given for each edge.

Output $$$n-1$$$ numbers $$$r_2, r_3, \dots, r_n$$$, where $$$r_i$$$ is defined as follows.

Consider the path from the root (vertex $$$1$$$) to $$$i$$$ ($$$2 \le i \le n$$$). Let the sum of the costs of $$$a_j$$$ along this path be $$$A_i$$$. Then $$$r_i$$$ is equal to the length of the maximum prefix of this path such that the sum of $$$b_j$$$ along this prefix does not exceed $$$A_i$$$.

Example for $$$n=9$$$. The blue color shows the costs of $$$a_j$$$, and the red color shows the costs of $$$b_j$$$.

Consider an example. In this case:

- $$$r_2=0$$$, since the path to $$$2$$$ has an amount of $$$a_j$$$ equal to $$$5$$$, only the prefix of this path of length $$$0$$$ has a smaller or equal amount of $$$b_j$$$;
- $$$r_3=3$$$, since the path to $$$3$$$ has an amount of $$$a_j$$$ equal to $$$5+9+5=19$$$, the prefix of length $$$3$$$ of this path has a sum of $$$b_j$$$ equal to $$$6+10+1=17$$$ ( the number is $$$17 \le 19$$$);
- $$$r_4=1$$$, since the path to $$$4$$$ has an amount of $$$a_j$$$ equal to $$$5+9=14$$$, the prefix of length $$$1$$$ of this path has an amount of $$$b_j$$$ equal to $$$6$$$ (this is the longest suitable prefix, since the prefix of length $$$2$$$ already has an amount of $$$b_j$$$ equal to $$$6+10=16$$$, which is more than $$$14$$$);
- $$$r_5=2$$$, since the path to $$$5$$$ has an amount of $$$a_j$$$ equal to $$$5+9+2=16$$$, the prefix of length $$$2$$$ of this path has a sum of $$$b_j$$$ equal to $$$6+10=16$$$ (this is the longest suitable prefix, since the prefix of length $$$3$$$ already has an amount of $$$b_j$$$ equal to $$$6+10+1=17$$$, what is more than $$$16$$$);
- $$$r_6=1$$$, since the path up to $$$6$$$ has an amount of $$$a_j$$$ equal to $$$2$$$, the prefix of length $$$1$$$ of this path has an amount of $$$b_j$$$ equal to $$$1$$$;
- $$$r_7=1$$$, since the path to $$$7$$$ has an amount of $$$a_j$$$ equal to $$$5+3=8$$$, the prefix of length $$$1$$$ of this path has an amount of $$$b_j$$$ equal to $$$6$$$ (this is the longest suitable prefix, since the prefix of length $$$2$$$ already has an amount of $$$b_j$$$ equal to $$$6+3=9$$$, which is more than $$$8$$$);
- $$$r_8=2$$$, since the path up to $$$8$$$ has an amount of $$$a_j$$$ equal to $$$2+4=6$$$, the prefix of length $$$2$$$ of this path has an amount of $$$b_j$$$ equal to $$$1+3=4$$$;
- $$$r_9=3$$$, since the path to $$$9$$$ has an amount of $$$a_j$$$ equal to $$$2+4+1=7$$$, the prefix of length $$$3$$$ of this path has a sum of $$$b_j$$$ equal to $$$1+3+3=7$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The descriptions of test cases follow.

Each description begins with a line that contains an integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — the number of vertices in the tree.

This is followed by $$$n-1$$$ string, each of which contains three numbers $$$p_j, a_j, b_j$$$ ($$$1 \le p_j \le n$$$; $$$1 \le a_j,b_j \le 10^9$$$) — the ancestor of the vertex $$$j$$$, the first and second values an edge that leads from $$$p_j$$$ to $$$j$$$. The value of $$$j$$$ runs through all values from $$$2$$$ to $$$n$$$ inclusive. It is guaranteed that each set of input data has a correct hanged tree with a root at the vertex $$$1$$$.

It is guaranteed that the sum of $$$n$$$ over all input test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, output $$$n-1$$$ integer in one line: $$$r_2, r_3, \dots, r_n$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first example is clarified in the statement.

In the second example:

- $$$r_2=0$$$, since the path to $$$2$$$ has an amount of $$$a_j$$$ equal to $$$1$$$, only the prefix of this path of length $$$0$$$ has a smaller or equal amount of $$$b_j$$$;
- $$$r_3=0$$$, since the path to $$$3$$$ has an amount of $$$a_j$$$ equal to $$$1+1=2$$$, the prefix of length $$$1$$$ of this path has an amount of $$$b_j$$$ equal to $$$100$$$ ($$$100 > 2$$$);
- $$$r_4=3$$$, since the path to $$$4$$$ has an amount of $$$a_j$$$ equal to $$$1+1+101=103$$$, the prefix of length $$$3$$$ of this path has an amount of $$$b_j$$$ equal to $$$102$$$, .

Example input:
4
9
1 5 6
4 5 1
2 9 10
4 2 1
1 2 1
2 3 3
6 4 3
8 1 3
4
1 1 100
2 1 1
3 101 1
4
1 100 1
2 1 1
3 1 101
10
1 1 4
2 3 5
2 5 1
3 4 3
3 1 5
5 3 5
5 2 1
1 3 2
6 2 1

Example output:
0 3 1 2 1 1 2 3 
0 0 3 
1 2 2 
0 1 2 1 1 2 2 1 1

Editorial:
Note that all $$$b_j$$$ are positive, which means that the amount on the prefix only increases. This allows us to use binary search to find the answer for the vertex. It remains only to learn how to quickly find the sum of $$$b_j$$$ on the path prefix. Let's run a depth-first search and store the prefix sums of the current path in stack: going to the vertex, add the sum to the end of the path and delete it when exiting.