A16512. Christmas Tree Un-decoration
编程题
省选/NOI-
知识点
题目描述
图 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$）。请注意这些更改具有持久性：每次更改的效果会持续到之后。
注意：你实际上并不会真的对树执行操作。
对于初始配置以及每次更改后的配置，你需要分别计算出当下移除所有装饰品所需的最少操作次数。
图 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$。
每个测试用例的第一行包含两个整数 $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
11 9 13 13 3 5 7 8 8 8 7
说明/提示
样例输入输出 #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 翻译
对于第一个测试用例，其初始树如图 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 翻译