题目描述

给定一棵有根树。它包含 $n$ 个顶点，编号从 $1$ 到 $n$。根为顶点 $1$。

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

输出 $n−1$ 个数字 $r_2,r_3,…,r_n$，其中 $r_i$ 定义如下

考虑从根（顶点 $1$）到 $i(2≤i≤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$ 总和更小或相等；
• $r_3=3$，因为到 $3$ 的路径上 $a_j$ 的总和等于 $5+9+5=19$，该路径长度为 $3$ 的前缀的 $b_j$ 总和为 $6+10+1=17(17≤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$。

输入格式

输入的第一行包含一个整数 $q (1≤q≤10^4)$ — 测试中的测试用例数量。

每个测试数据的第一行是整数 $n(2≤n≤2×10^5)$ ，表示树中的节点数。

接下来的 $n−1$ 行，每行包含三个数字 $p_j,a_j,b_j (1≤p_j≤n; 1≤a_j,b_j≤10^9)$ ，表示从节点 $p_j$ 连向节点 $j$ 的边，其中 $a_j$ 和 $b_j$ 分别是这条边的两个权值。保证输入数据构成一棵正确的有根树，以节点 $1$ 为根。

保证所有测试数据中 $n$ 的总和不超过 $2×10^5$。

输出格式

每个测试用例输出 $n−1$ 个整数，用一行表示：$r_2,r_3,…,r_n$。

测试样例

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

0 3 1 2 1 1 2 3 
0 0 3 
1 2 2 
0 1 2 1 1 2 2 1 1

样例说明

解释如下：

• 对于节点 $2$，沿着根节点 $1$ 到 $2$ 的路径只有一条边，权值为 $1$，因此 $r_2=0$。
• 对于节点 $3$，沿着根节点 $1$ 到 $3$ 的路径上有两条边，权值分别为 $1$ 和 $1$，因此路径上所有边的权值之和为 $2$。路径的前缀只能是长度为 $0$ 的空前缀，因为加上第一条边的权值后就已经大于了 $b_j$ 的值，即 $r_i=0$。
• 对于节点 $4$，沿着根节点 $1$ 到 $4$ 的路径上有三条边，权值分别为 $1$、$1$ 和 $101$。路径上所有边的权值之和为 $103$。路径的前缀可以是长度为 $3$ 的前缀，因为加上前两条边的权值后，边权之和为 $2$，小于等于 $b_j$ 的值。而加上前三条边的权值后，边权之和为 $102$，大于 $b_j$ 的值，因此 $r_i=3$。