CF1942H.Farmer John's Favorite Intern

Peaches...

⠀

Ruby 刚刚通过编程竞赛赢得了 Farmer John 农场的实习机会！作为新招募的实习生，Ruby 的任务是维护 Farmer John 的桃树，这棵树有 $n$ 个结点，以结点 $1$ 为根。每个结点初始时有 $a_i = 0$ 个桃子，并且有两种事件可能发生：

1. 在某个结点 $x$ 处的生长事件：Ruby 必须选择 $x$ 的父结点或 $x$ 的子树中的任意一个结点，并将其桃子数量增加 $1$。
2. 在某个结点 $x$ 处的收获事件：Ruby 必须选择 $x$ 的子树中的一个结点，并将其桃子数量减少 $1$。注意，这与生长事件可选的结点集合不同。

注意，$x$ 的子树包括结点 $x$ 本身。Ruby 还得到了一个长度为 $n$ 的数组 $b$。当且仅当对每个结点 $i$ 都有 $a_i \ge b_i$ 时，这棵桃树才被认为是健康的。

Ruby 需要执行 $q$ 个操作，操作有两种类型：

• 1 x v — 在结点 $x$ 上执行 $v$ 次生长事件。Ruby 每次可以选择不同的结点进行增加。
• 2 x v — 在结点 $x$ 上执行 $v$ 次收获事件。Ruby 每次可以选择不同的结点进行减少。

对于每个操作前缀，Ruby 想知道是否存在一种顺序执行这些操作的方法，使得最终的桃树是健康的。注意，Ruby 不能执行会导致某个 $a_i$ 变为负数的收获事件。

每个前缀互相独立，也就是说，对于某个操作，Ruby 可以在包含该操作的每个前缀中选择不同的结点来执行事件。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$）——表示树的结点数和操作数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$）——表示每个结点的父结点编号。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 10^6$）——表示每个结点所需的最少桃子数。

接下来的 $q$ 行，每行描述一个操作，包含三个整数 $t, x, v$（$1 \le t \le 2$，$1 \le x \le n$，$1 \le v \le 10^6$）。如果 $t=1$，表示在结点 $x$ 上执行 $v$ 次生长事件；如果 $t=2$，表示在结点 $x$ 上执行 $v$ 次收获事件。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，$q$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $q$ 行。第 $i$ 行输出 "YES"（不区分大小写），如果 Ruby 能够在某种顺序下完成前 $i$ 个操作后使桃树健康，否则输出 "NO"。

你可以用任意大小写输出答案，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。

对于第一个测试用例中包含操作 $1, 2, \ldots, 5$ 的前缀，Ruby 可以按如下顺序执行操作：

1. Ruby 执行操作 $2$，选择将 $a_4$ 增加 $9$，$a_5$ 增加 $8$。
2. Ruby 执行操作 $1$，选择将 $a_1$ 增加 $5$，$a_3$ 增加 $2$，$a_6$ 增加 $4$，$a_8$ 增加 $3$。
3. Ruby 执行操作 $3$，选择将 $a_2$ 增加 $7$。
4. Ruby 执行操作 $4$，选择将 $a_2$ 减少 $1$。
5. Ruby 执行操作 $5$，选择将 $a_7$ 增加 $1$。

由 ChatGPT 4.1 翻译