给定一棵有根树,根位于顶点 $$$1$$$。对于树中的任何顶点 $$$i$$$ ($$$1 < i \leq n$$$),都有一条边连接顶点 $$$i$$$ 和 $$$p_i$$$ ($$$1 \leq p_i < i$$$),其权重等于 $$$t_i$$$。
Iris 不知道 $$$t_i$$$ 的值,但她知道 $$$\displaystyle\sum_{i=2}^n t_i = w$$$ 并且每个 $$$t_i$$$ 都是非负整数。
树的顶点以特殊的方式进行编号:每个子树中的顶点编号都是连续的整数。换句话说,树的顶点按照深度优先搜索的顺序进行编号。
这张图中的树满足条件。例如,顶点$$$2$$$的子树中,顶点编号为$$$2,3,4,5$$$,均为连续整数。
该图中的树不满足条件,因为在顶点$$$2$$$的子树中,顶点编号$$$2$$$和$$$4$$$不是连续的整数。
我们将 $$$\operatorname{dist}(u, v)$$$ 定义为树中顶点 $$$u$$$ 和 $$$v$$$ 之间的简单路径的长度。
接下来,将有 $$$n - 1$$$ 事件:
- Iris 被赋予整数 $$$x$$$ 和 $$$y$$$,表示 $$$t_x = y$$$。
在每个事件之后,Iris 想知道每个 $$$i$$$ 独立的 $$$\operatorname{dist}(i, i \bmod n + 1)$$$ 的最大可能值 ($$$1\le i\le n$$$)。她只需要知道这些 $$$n$$$ 值的总和。请帮助 Iris 快速找到答案。
请注意,在计算 $$$i \ne j$$$ 的 $$$\operatorname{dist}(i, i \bmod n + 1)$$$ 和 $$$\operatorname{dist}(j, j \bmod n + 1)$$$ 的最大可能值时,未知边权重可能不同。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$w$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \leq w \leq 10^{12}$$$) - 树中的顶点数和边权重之和。
每个测试用例的第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$) - 树边的描述。
然后按照 $$$n-1$$$ 行指示事件。每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$2 \leq x \leq n$$$, $$$0 \leq y \leq w$$$),表示 $$$t_x = y$$$。
保证事件中的所有 $$$x$$$ 都是不同的。还保证所有 $$$y$$$ 的总和等于 $$$w$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含 $$$n-1$$$ 整数,每个整数代表每个事件后的答案。
示例
输入 #1
4 2 1000000000000 1 2 1000000000000 4 9 1 1 1 2 2 4 4 3 3 6 100 1 2 3 2 1 6 17 3 32 2 4 4 26 5 21 10 511 1 2 2 4 2 1 1 8 8 3 2 6 16 10 256 9 128 2 1 5 8 8 64 4 4 7 32
输出 #1
2000000000000 25 18 18 449 302 247 200 200 4585 4473 2681 1567 1454 1322 1094 1022 1022
注意
在第一个测试用例中, $$$\operatorname{dist}(1, 2) = \operatorname{dist}(2, 1) = t_2 = w = 10^{12}$$$,因此 $$$\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 2 \cdot 10^{12}$$$。
在第二个测试用例中,Iris 找到所有 $$$t_x$$$ 后的树如下所示:
$$$\operatorname{dist}(1, 2) = t_2$$$, $$$\operatorname{dist}(2, 3) = t_2 + t_3$$$, $$$\operatorname{dist}(3, 4) = t_3 + t_4$$$, $$$\operatorname{dist}(4, 1) = t_4$$$。在第一个事件之后,她发现 $$$t_2 = 2$$$,因此 $$$\operatorname{dist}(1, 2) = 2$$$。同时:
- 如果 $$$t_3 = 7$$$、$$$t_4 = 0$$$,则 $$$\operatorname{dist}(2, 3)$$$ 最大化。那么 $$$\operatorname{dist}(2, 3) = 9$$$。
- 如果 $$$t_3 = 0$$$、$$$t_4 = 7$$$,则 $$$\operatorname{dist}(3, 4)$$$ 和 $$$\operatorname{dist}(4, 1)$$$ 最大化。然后 $$$\operatorname{dist}(3, 4) = \operatorname{dist}(4, 1) = 7$$$。
因此,答案是 $$$2 + 9 + 7 + 7 = 25$$$。
第二个事件之后,她发现$$$t_4 = 4$$$,然后$$$t_3 = w - t_2 - t_4 = 4$$$。 $$$\operatorname{dist}(1, 2) = 2$$$, $$$\operatorname{dist}(2, 3) = 2 + 3 = 5$$$, $$$\operatorname{dist}(3, 4) = 3 + 4 = 7$$$, $$$\operatorname{dist}(4, 1) = 4$$$。因此,答案是$$$2 + 5 + 7 + 4 = 18$$$。