← 返回题目列表

Codeforces · 1942/H

H. 农夫约翰最喜欢的实习生

中文机器翻译题面 查看原题

Ruby 刚刚通过赢得编码比赛赢得了 Farmer John 农场的实习职位!作为新招募的实习生,Ruby 的任务是维护 Farmer John 的桃树,该树由 $$$n$$$ 节点组成,根节点为 $$$1$$$。每个节点最初包含 $$$a_i = 0$$$ 桃子,并且可能发生两种类型的事件:

1. 某个节点 $$$x$$$ 处的增长事件:Ruby 必须选择 $$$x$$$ 的父节点或 $$$x$$$ 子树中的任何节点,并将其包含的桃子数量增加 1。
2. 某个节点 $$$x$$$ 处的收获事件:Ruby 必须选择 $$$x$$$ 子树中的单个节点,并将其包含的桃子数量减少 1。请注意,这与增长事件不是同一组节点。

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 \cdot 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$$$ 行描述 Ruby 将执行的操作。每行包含三个整数 $$$t$$$、$$$x$$$ 和 $$$v$$$ ($$$1 \le t \le 2$$$、$$$1 \le x \le n$$$、$$$1 \le v \le 10^6$$$)。如果 $$$t = 1$$$,这表示 Ruby 必须在节点 $$$x$$$ 上执行 $$$v$$$ 增长事件。如果 $$$t = 2$$$,则表示 Ruby 必须在节点 $$$x$$$ 上执行 $$$v$$$ 收获事件。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$,$$$q$$$之和不超过$$$2 \cdot 10^5$$$

输出

对于每个测试用例,输出 $$$q$$$ 行。如果 Ruby 在按某种顺序执行操作 $$$1, 2, \ldots, i$$$ 后可以使桃树健康,那么第 $$$i$$$ 行应该包含“YES”。否则,它应该包含“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

2
8 8
1 1 1 4 3 6 6
5 6 2 9 8 4 1 3
1 3 14
1 4 17
1 2 7
2 2 1
1 6 1
2 1 1000000
1 4 999999
1 3 1
10 20
1 1 1 2 5 2 4 7 2
311353 270334 74853 385085 315501 183346 234819 417314 103862 429437
1 1 837541
1 10 933876
1 1 565958
1 4 791455
2 3 85054
2 3 440978
1 4 981040
1 5 68522
2 1 858305
2 4 184308
1 4 905081
2 8 519626
2 2 269090
1 1 43016
2 2 517644
1 5 355792
1 9 319241
2 10 125447
2 10 523890
1 10 241045

输出 #1

NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO

注意

对于第一个测试用例中包含操作 $$$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$$$。