CF1714G.Path Prefixes

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$.

你被给定一棵有根树，该树包含 $n$ 个顶点，编号从 $1$ 到 $n$，其中根节点为顶点 $1$。

每条边有两个正整数权值。因此，对每条边 $j$，给出两个正整数 $a_j$ 和 $b_j$。

请输出 $n-1$ 个数 $r_2, r_3, \dots, r_n$，其中 $r_i$ 的定义如下：

考虑从根节点（顶点 $1$）到顶点 $i$（$2 \le i \le n$）的路径。设该路径上所有边的 $a_j$ 值之和为 $A_i$。则 $r_i$ 表示该路径的最长前缀长度，使得该前缀上所有边的 $b_j$ 值之和不超过 $A_i$。

$n=9$ 的示例。蓝色表示 $a_j$ 的权值，红色表示 $b_j$ 的权值。

我们来看一个例子。在该例中：

• $r_2=0$，因为到顶点 $2$ 的路径上 $a_j$ 的总和为 $5$，而该路径长度为 $0$ 的前缀（即空路径）对应的 $b_j$ 总和为 $0$（满足 $\le 5$），但长度为 $1$ 的前缀的 $b_j$ 总和已超过 $5$；
• $r_3=3$，因为到顶点 $3$ 的路径上 $a_j$ 的总和为 $5+9+5=19$，该路径长度为 $3$ 的前缀的 $b_j$ 总和为 $6+10+1=17$（满足 $17 \le 19$）；
• $r_4=1$，因为到顶点 $4$ 的路径上 $a_j$ 的总和为 $5+9=14$，该路径长度为 $1$ 的前缀的 $b_j$ 总和为 $6$（这是满足条件的最长前缀，因为长度为 $2$ 的前缀的 $b_j$ 总和为 $6+10=16 > 14$）；
• $r_5=2$，因为到顶点 $5$ 的路径上 $a_j$ 的总和为 $5+9+2=16$，该路径长度为 $2$ 的前缀的 $b_j$ 总和为 $6+10=16$（这是满足条件的最长前缀，因为长度为 $3$ 的前缀的 $b_j$ 总和为 $6+10+1=17 > 16$）；
• $r_6=1$，因为到顶点 $6$ 的路径上 $a_j$ 的总和为 $2$，该路径长度为 $1$ 的前缀的 $b_j$ 总和为 $1$；
• $r_7=1$，因为到顶点 $7$ 的路径上 $a_j$ 的总和为 $5+3=8$，该路径长度为 $1$ 的前缀的 $b_j$ 总和为 $6$（这是满足条件的最长前缀，因为长度为 $2$ 的前缀的 $b_j$ 总和为 $6+3=9 > 8$）；
• $r_8=2$，因为到顶点 $8$ 的路径上 $a_j$ 的总和为 $2+4=6$，该路径长度为 $2$ 的前缀的 $b_j$ 总和为 $1+3=4$；
• $r_9=3$，因为到顶点 $9$ 的路径上 $a_j$ 的总和为 $2+4+1=7$，该路径长度为 $3$ 的前缀的 $b_j$ 总和为 $1+3+3=7$。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

随后是各测试用例的描述。

每个测试用例的描述以一行开始，该行包含一个整数 $n$（$2 \le n \le 2\cdot10^5$）—— 树中顶点的数量。

接下来是 $n-1$ 行字符串，每行包含三个数 $p_j, a_j, b_j$（$1 \le p_j \le n$；$1 \le a_j,b_j \le 10^9$）—— 分别表示顶点 $j$ 的父节点、从 $p_j$ 指向 $j$ 的边的第一个值和第二个值。其中 $j$ 取遍从 $2$ 到 $n$（含）的所有整数。保证每组输入数据均构成一棵以顶点 $1$ 为根的合法有根树。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

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

对于每个测试用例，在一行中输出 $n-1$ 个整数：$r_2, r_3, \dots, r_n$。

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 \gt 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$, .

第一个示例在题面中已作说明。

第二个示例中：

• $r_2=0$，因为到达节点 $2$ 的路径上 $a_j$ 的总和为 $1$，该路径中仅有长度为 $0$ 的前缀满足其 $b_j$ 的总和小于等于 $1$；
• $r_3=0$，因为到达节点 $3$ 的路径上 $a_j$ 的总和为 $1+1=2$，该路径中长度为 $1$ 的前缀的 $b_j$ 总和为 $100$（$100 \gt 2$）；
• $r_4=3$，因为到达节点 $4$ 的路径上 $a_j$ 的总和为 $1+1+101=103$，该路径中长度为 $3$ 的前缀的 $b_j$ 总和为 $102$。