← 返回题目列表

AtCoder · njpc2017_h

H. 黑白树

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

配点 : 1000 点

問題文

N 我们得到了一棵有根的顶点树。在每个顶点 1, 2, …, N 已编号,顶点为 1 是这棵有根树的根。所有边都是无向的,i 番目 ( 2 ≦ i ≦ N ) 的顶点的父级是 p_i 。

最初,每个顶点都被漆成白色或黑色;i 第一个顶点 ( 1 ≦ i ≦ N ) 的初始颜色是 白色时 C_i = 0 ,C_i = 1 是黑色的。 您将收到

Q 查询,因此请按顺序处理。查询可以是以下两种类型之一,查询的输入格式和内容如下。 反转以

  • 1 u:頂点 u 为根的子树中所有顶点的颜色。 如果交替通过白色顶点和黑色顶点可以到达
  • 2 u v:頂点 u 它们的编号最大为 v ,YES,否则NO。第一种颜色可以是白色或黑色。

制約

  • 所有输入均为整数。
  • 2≦N≦10^5
  • 1≦p_i≦N
  • C_i = 0 或 1
  • 1≦Q≦10^5
  • 输入有根树始终是连接的。
  • 查询是 保证至少有一个格式为1 u时, 除以1≦u≦N 。
  • 查询是 保证至少有一个格式为2 u v时, 除以1≦u,v≦N 和 u≠v 。
  • 2 u v的查询。 以

入力

输入将以以下形式通过标准输入给出。

N
p_2
p_3
:
p_N
C_1
C_2
:
C_N
Q
query_1
query_2
:
query_Q

出力

2 u v格式输出查询的答案,按照给出查询的顺序,每行一行。


入力例 1

6
1
1
2
2
3
0
1
0
0
1
1
10
2 4 1
2 4 3
2 1 2
1 2
2 4 1
1 3
1 5
2 1 6
1 1
2 5 4

出力例 1

YES
NO
YES
NO
YES
YES

入力例 2

7
1
2
3
3
5
6
0
0
1
0
0
1
1
7
2 1 4
2 4 2
2 4 5
2 4 6
2 6 1
2 7 1
2 2 6

出力例 2

NO
YES
YES
YES
NO
NO
YES

入力例 3

2
1
0
1
11
2 1 2
2 2 1
1 2
2 1 2
2 2 1
1 1
2 1 2
2 2 1
1 2
2 1 2
2 2 1

出力例 3

YES
YES
NO
NO
NO
NO
YES
YES

入力例 4

5
1
2
3
4
0
1
0
1
0
11
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5
1 3
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5

出力例 4

YES
YES
YES
YES
YES
YES
NO
NO
NO
YES

入力例 5

9
4
2
6
8
1
4
1
8
0
0
1
0
0
1
1
1
0
2
2 9 8
2 9 4

出力例 5

YES
YES