← 返回题目列表

AtCoder · kupc2021_i

I. 好缺乏

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

配点 : 400 点

問題文

N 顶点的有根树。在每个顶点 编号为 1 它们的编号最大为 N 的顶点 1 是根。 顶点 i (2 \leq i \leq N ) 的父级是 P_i 。

每个顶点都有一个玩具箱。此外,每个顶点都有一个人。

开始,顶点 i 玩具箱里有玩具。 A_i 块。

另外,顶点 i 中的人有玩具。 目标是收集 C_i 。在这里, 位于

  • 頂点 i 的人位于顶部 您可以从以 i 为根的子树中选择一些顶点,并从每个选定的顶点中获取任意数量的玩具。

。

确定是否可以同时实现每个人的目标。 (但是,多个人不能拿同一个玩具。) 给出

此外, 如果你按照 Q 查询。 在第 i 个查询中,整数 给定 t_i,v_i,x_i ,按如下方式更改值: 更改为

  • t_i = 1 什么时候 A_{v_i} 的值 替换为 x_i 更改为
  • t_i = 2 什么时候 C_{v_i} 的值 替换为 x_i 更改为

每次查询后,确定是否有可能同时实现每个人的目标。

但请注意,在确定是否有可能同时实现每个人的目标时,实际上没有移动任何玩具。 (也就是说,每个判断都是独立考虑的。)

制約

  • 1 \leq N \leq 10^5
  • 1 \leq P_i < i (2 \leq i \leq N )
  • 1 \leq A_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq Q \leq 10^5
  • t_i \in \{ 1 , 2 \}
  • 1 \leq v_i \leq N
  • 1 \leq x_i \leq 10^9
  • 所有输入均为整数

入力

输入将以以下格式从标准输入提供。

N
P_2 \cdots P_N
A_1 \cdots A_N
C_1 \cdots C_N
Q
t_1 v_1 x_1
t_2 v_2 x_2
:
t_Q v_Q x_Q

出力

如果有可能在每个时间点同时实现每个人的目标 Yes 如果不可能 No 的 1 请输出每一行。

也就是说,初始状态下的答案是 1 行上,i (1 \leq i \leq Q ) 查询后的答案是 请在 i + 1 行输出。


入力例 1

3
1 1
2 1 3
3 1 2
2
1 1 1
2 3 1

出力例 1

Yes
No
Yes

一开始,

  • 頂点 1 人们在顶部 1 玩具盒中的玩具 2 個、 頂点 3 玩具盒中的玩具 1 采取
  • 頂点 2 人们在顶部 2 玩具盒中的玩具 1 采取
  • 頂点 3 人们在顶部 3 玩具盒中的玩具 2 采取

让每个人都能同时实现自己的目标。

通过处理第一个查询,顶点 1 玩具箱中的玩具数量为 来自 2 件 1 变化。在这种情况下,无论每个人如何选择玩具,都不可能同时实现每个人的目标。

通过处理第二个查询,顶点 3 人们想要多少玩具? 2 件 1 变化。 在这种情况下,

  • 頂点 1 人们在顶部 1 玩具盒中的玩具 1 個、 頂点 3 玩具盒中的玩具 2 采取
  • 頂点 2 人们在顶部 2 玩具盒中的玩具 1 采取
  • 頂点 3 人们在顶部 3 玩具盒中的玩具 1 采取

让每个人都能同时实现自己的目标。


入力例 2

5
1 2 1 3
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1
1
1 1 1

出力例 2

Yes
Yes

玩具的总数可能非常大。


入力例 3

5
1 2 2 2
109102235 645590056 708566822 497603443 131863700
50073184 441114664 164994352 304489019 158100373
8
1 5 692234112
1 3 610338520
2 4 818442884
2 4 164762830
2 4 923652447
2 4 197720766
1 1 779302743
1 1 222486377

出力例 3

No
Yes
Yes
No
Yes
No
Yes
Yes
Yes