← 返回题目列表

Codeforces · 1714/G

G. 路径前缀

中文机器翻译题面 查看原题

你得到了一棵有根的树。它包含 $$$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$$$,。