![]() |
| 图 D.1:圣诞树。 |
去年圣诞节,你度过了一个可爱的圣诞节 树 具有 $$$n$$$ 个顶点,编号从 $$$1$$$ 到 $$$n$$$,并以顶点 $$$1$$$ 为根。对于每个 $$$i$$$ ($$$2 \le i \le n$$$),顶点 $$$p_i$$$ 是顶点 $$$i$$$ 的父节点。这棵树的顶点 $$$i$$$ ($$$1 \le i \le n$$$) 上装饰着精美的 $$$a_i$$$ 装饰品。
然而,圣诞节已经过去几个月了,是时候把所有的装饰品都拿下来,把你的圣诞树收起来,直到明年。由于此过程很乏味,您决定仅使用以下操作来使其变得更有趣,您可以执行零次或多次:
| 选择一个顶点$$$u$$$。对于从顶点 $$$1$$$ 到顶点 $$$u$$$ (包含)的唯一简单路径上的每个顶点 $$$v$$$,从 $$$v$$$ 中恰好删除一个装饰(如果有剩余)。 |
当您仍在确定所需的最少操作次数时,您的小孩修改了树上装饰品的数量。更准确地说,您的孩子做出了 $$$q$$$ 改变。在第 $$$j$$$ 次更改中,顶点 $$$u_j$$$ 上的装饰物数量修改为 $$$x_j$$$ ($$$1 \le j \le q$$$)。请注意,这些更改是持久的;每个更改的影响都会延续到后续更改。
请注意,您实际上并未对树执行任何操作。
对于初始配置和每次更改后,您的任务是确定每次从树上删除所有装饰品所需的最少操作数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) 表示测试用例的数量。之后,$$$t$$$ 测试用例如下。它们各自介绍如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$; $$$1 \le q \le 200\,000$$$)。第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$ 对于所有 $$$2 \le i \le n$$$)。第三行包含$$$n$$$整数$$$a_1、a_2、\ldots、a_n$$$(对于所有$$$1 \le i \le n$$$,$$$1 \le a_i \le 10^9$$$)。
接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$u_j$$$ 和 $$$x_j$$$ ($$$1 \le u_j \le n$$$; $$$1 \le x_j \le 10^9$$$)。
一个输入文件中所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。
一个输入文件中所有测试用例的 $$$q$$$ 总和不超过 $$$200\,000$$$。
输出
对于每个测试用例,输出 $$$q+1$$$ 行。第一行应包含初始树所需的最少操作数。以下 $$$q$$$ 行中的第 $$$j$$$ 行应包含发生第 $$$j$$$ 次更改后所需的最少操作数。
示例
输入复制
2 6 3 1 1 2 3 3 5 3 2 5 2 4 4 1 3 10 1 6 8 6 1 2 3 4 5 5 3 1 1 1 1 1 1 1 1 6 3 8 3 5 5 6 1 3 7 5 1
输出复制
11 9 13 13 3 5 7 8 8 8 7
注意
示例输入/输出#1 的说明
对于第一个测试用例,其初始树如图 D.1 所示。请注意,图中顶点 $$$1$$$ 处的星星也是一个装饰品。
- 在初始树中,您可以通过选择顶点 $$$4$$$ 五次、顶点 $$$5$$$ 两次和顶点 $$$6$$$ 四次来删除具有 $$$11$$$ 操作的所有装饰物。
- 第一次更改后,顶点上只有一个装饰 $$$4$$$。您需要 $$$9$$$ 操作;选择顶点$$$4$$$一次,顶点$$$2$$$两次,顶点$$$5$$$两次,以及顶点$$$6$$$四次。
- 第二次变化后,顶点上有十个装饰品$$$3$$$。您需要 $$$13$$$ 操作。
- 第三次变化后,顶点上有六个装饰品$$$1$$$。然而,所需的操作次数没有改变。
