CF2206D.Christmas Tree Un-decoration

Figure D.1: Christmas tree.

Last Christmas, you had a lovely Christmas tree with $n$ vertices, numbered from $1$ to $n$ and rooted at vertex $1$. For each $i$ ($2 \le i \le n$), vertex $p_i$ is the parent of vertex $i$. The tree is decorated beautifully with $a_i$ ornaments on vertex $i$ ($1 \le i \le n$).

However, it has already been a few months since Christmas, and it is time to take down all the ornaments and put your tree away until next year. Since this process is tedious, you have decided to make it more fun by using only the following operation, which you can perform zero or more times:

Choose a vertex $u$. For each vertex $v$ on the unique simple path from vertex $1$ to vertex $u$ (inclusive), remove exactly one ornament from $v$ if there is any left.

While you are still determining the minimum number of operations needed, your little child modifies the number of ornaments on the tree. More precisely, your child makes $q$ changes. In the $j$-th change, the number of ornaments on vertex $u_j$ is modified to $x_j$ ($1 \le j \le q$). Note that these changes are persistent; the effect of each change carries over to subsequent changes.

Note that you do not actually perform any operations on the tree.

For the initial configuration and after each change, your task is to determine the minimum number of operations needed to remove all the ornaments from the tree at each moment.

图 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$ 上尚有装饰品，则恰好移除其中 1 个。

在你尚在计算所需最少操作次数时，你的小孩修改了树上各顶点的装饰品数量。具体而言，小孩共进行了 $q$ 次修改。在第 $j$ 次修改中（$1 \le j \le q$），顶点 $u_j$ 上的装饰品数量被更改为 $x_j$。注意，这些修改是持久性的；每次修改的效果将延续至后续所有修改。

请注意，你实际上并未对树执行任何操作。

对于初始配置以及每次修改之后的状态，你的任务是：分别求出在该时刻清空整棵树上所有装饰品所需的最少操作次数。

The first line of input contains one integer $t$ ($1 \le t \le 10\,000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le 200\,000$; $1 \le q \le 200\,000$). The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \lt i$ for all $2 \le i \le n$). The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$ for all $1 \le i \le n$).

The $j$-th of the next $q$ lines contains two integers $u_j$ and $x_j$ ($1 \le u_j \le n$; $1 \le x_j \le 10^9$).

The sum of $n$ across all test cases in one input file does not exceed $200\,000$.

The sum of $q$ across all test cases in one input file does not exceed $200\,000$.

输入的第一行包含一个整数 $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 \lt i$）。
第三行包含 $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$。

For each test case, output $q+1$ lines. The first line should contain the minimum number of operations required for the initial tree. The $j$-th of the following $q$ lines should contain the minimum number of operations required after the $j$-th change happens.

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

Explanation for the sample input/output #1

For the first test case, its initial tree is illustrated in Figure D.1. Note that the star at vertex $1$ in the figure is also an ornament.

• In the initial tree, you can remove all ornaments with $11$ operations by choosing vertex $4$ five times, vertex $5$ twice, and vertex $6$ four times.
• After the first change, there is only one ornament on vertex $4$. You need $9$ operations; choose vertex $4$ once, vertex $2$ twice, vertex $5$ twice, and vertex $6$ four times.
• After the second change, there are ten ornaments on vertex $3$. You need $13$ operations.
• After the third change, there are six ornaments on vertex $1$. However, the required number of operations is unchanged.

样例输入/输出 #1 的说明

对于第一个测试用例，其初始树如图 D.1 所示。注意：图中顶点 $1$ 上的星形符号同样是一种装饰物（ornament）。

• 在初始树中，你可以通过 $11$ 次操作移除所有装饰物：选择顶点 $4$ 五次、顶点 $5$ 两次、顶点 $6$ 四次。
• 第一次修改后，顶点 $4$ 上仅剩一个装饰物。此时你需要 $9$ 次操作：选择顶点 $4$ 一次、顶点 $2$ 两次、顶点 $5$ 两次、顶点 $6$ 四次。
• 第二次修改后，顶点 $3$ 上有十个装饰物。此时你需要 $13$ 次操作。
• 第三次修改后，顶点 $1$ 上有六个装饰物。然而，所需的操作次数保持不变。