你得到了一棵有根的树。它包含 $$$n$$$ 个顶点,编号从 $$$1$$$ 到 $$$n$$$。根是顶点$$$1$$$。
每条边都有两个正整数值。因此,为每条边给出两个正整数 $$$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$$$的数量;
- $$$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$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,在一行中输出 $$$n-1$$$ 整数:$$$r_2, r_3, \dots, r_n$$$。
示例
输入 #1
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
输出 #1
0 3 1 2 1 1 2 3 0 0 3 1 2 2 0 1 2 1 1 2 2 1 1
注意
第一个例子在声明中得到了澄清。
在第二个示例中:
- $$$r_2=0$$$,由于到$$$2$$$的路径的$$$a_j$$$的数量等于$$$1$$$,因此只有这条长度为$$$0$$$的路径的前缀具有小于或等于$$$b_j$$$的数量;
- $$$r_3=0$$$,由于到$$$3$$$的路径的数量$$$a_j$$$等于$$$1+1=2$$$,因此该路径的长度$$$1$$$的前缀的数量$$$b_j$$$等于$$$100$$$ ($$$100 > 2$$$);
- $$$r_4=3$$$,由于到$$$4$$$的路径的数量$$$a_j$$$等于$$$1+1+101=103$$$,因此该路径的长度$$$3$$$的前缀的数量$$$b_j$$$等于$$$102$$$,。