CFCF2206D.Christmas Tree Un-decoration

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

图 D.1：圣诞树。
去年圣诞节，你有一棵漂亮的圣诞树，这棵树有 $n$ 个结点，编号为 $1$ 到 $n$ ，以结点 $1$ 作为根。对于每个 $i$ （ $2 \le i \le n$ ），结点 $p_i$ 是结点 $i$ 的父亲。树上的每个结点 $i$ 上装饰有 $a_i$ 个装饰品（ $1 \le i \le n$ ）。

然而圣诞节已过了几个月，是时候摘下所有的装饰品，把树收起来等到明年再用了。由于这个过程很单调，你决定通过只使用如下操作让它变得有趣些——你可以进行零次甚至多次如下操作：

选择一个结点 $u$ ，对于从结点 $1$ 到结点 $u$ 的唯一简单路径上的每个结点 $v$ （包括 $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$ （对所有 $2 \le i \le n$ ，有 $1 \le p_i < i$ ）。第三行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （对所有 $1 \le i \le n$ ， $1 \le a_i \le 10^9$ ）。

接下来的 $q$ 行，每一行包含两个整数 $u_j$ 和 $x_j$ （ $1 \le u_j \le n$ ； $1 \le x_j \le 10^9$ ），表示第 $j$ 次修改的信息。

所有测试用例中 $n$ 的总和不超过 $200\,000$ 。

所有测试用例中 $q$ 的总和不超过 $200\,000$ 。

输出格式

对于每个测试用例，输出 $q+1$ 行。第一行输出初始树所需的最小操作次数。接下来的第 $j$ 行输出第 $j$ 次修改后最少需要的操作次数。

输入输出样例

输入#1

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

输出#1

说明/提示

样例输入输出 #1 说明：

对于第一个测试用例，其初始树如图 D.1 所示。注意，图中的星星（结点 $1$ ）也是一个装饰品。

对于初始树，你可以通过选择结点 $4$ 5 次、结点 $5$ 2 次、结点 $6$ 4 次，总共 $11$ 次操作移除所有装饰品。
第一次修改后，结点 $4$ 上只有一个装饰品。你需要 $9$ 次操作，依次选择结点 $4$ 1 次、结点 $2$ 2 次、结点 $5$ 2 次、结点 $6$ 4 次。
第二次修改后，结点 $3$ 上有 $10$ 个装饰品。你需要 $13$ 次操作。
第三次修改后，结点 $1$ 上有 $6$ 个装饰品，但所需操作次数并未改变。

由 ChatGPT 5 翻译

首页