题目描述

去年圣诞节，你有一棵漂亮的圣诞树，这棵树有 $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

输入 #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 翻译