← 返回题目列表

Codeforces · 2206/D

D. 圣诞树未装饰

中文机器翻译题面 查看原题
图 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$$$。然而,所需的操作次数没有改变。