B. Iris 与树

时间限制：3 秒
内存限制：256 MB

给定一棵以顶点 $1$ 为根的树。对于树中的任意顶点 $i$（$1 < i \le n$），存在一条连接顶点 $i$ 和 $p_i$（$1 \le p_i < i$）的边，其权值为 $t_i$。

Iris 不知道 $t_i$ 的值，但她知道 $\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$（$1 \le i \le n$），$\operatorname{dist}(i, i \bmod n + 1)$ 可能的最大值。她只需要知道这 $n$ 个值的和。请帮助 Iris 快速得到答案。

注意：当计算不同 $i$ 对应的 $\operatorname{dist}(i, i \bmod n + 1)$ 的最大值时，未知的边权可以不同。

---

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $w$（$2 \le n \le 2 \cdot 10^5$，$0 \le w \le 10^{12}$）—— 树中的顶点数以及边权之和。

每个测试用例的第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i < i$）—— 树的边描述。

接下来的 $n-1$ 行表示事件。每行包含两个整数 $x$ 和 $y$（$2 \le x \le n$，$0 \le y \le w$），表示 $t_x = y$。

保证所有事件中的 $x$ 互不相同。同时保证所有 $y$ 的和等于 $w$。

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

---

输出格式

对于每个测试用例，输出一行，包含 $n-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

输出

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$。同时：

• $\operatorname{dist}(2,3)$ 在 $t_3 = 7$、$t_4 = 0$ 时取最大值 $9$
• $\operatorname{dist}(3,4)$ 和 $\operatorname{dist}(4,1)$ 在 $t_3 = 0$、$t_4 = 7$ 时取最大值 $7$

因此答案为 $2 + 9 + 7 + 7 = 25$。

第二个事件后，她知道 $t_4 = 4$，则 $t_3 = w - t_2 - t_4 = 3$。
$\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$。