← 返回题目列表

Codeforces · 2006/B

B. 鸢尾花和树

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

给定一棵有根树,根位于顶点 $$$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$$$。