H - 白黒ツリー 解説 /

実行時間制限: 5 sec / メモリ制限: 256 MB

配点 : 1000 点

問題文

N 頂点の根付き木が与えられます。各頂点には 1, 2, …, N と番号がつけられており，頂点 1 はこの根付き木の根です。辺はすべて無向辺で，i 番目 ( 2 ≦ i ≦ N ) の頂点の親は p_i です。

最初，各頂点は白または黒に塗られており，i 番目の頂点 ( 1 ≦ i ≦ N ) の初期の色は C_i = 0 のとき白色，C_i = 1 のとき黒色です。

Q 個のクエリが与えられるので，順番に処理してください。クエリは以下の2種類のどちらかで，入力形式とクエリの内容は以下のとおりです。

  • 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というフォーマットのクエリが少なくとも1つ存在することが保証される。

入力

入力は以下の形式で標準入力から与えられる。

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

出力

2 u vというフォーマットのクエリに対する答えを，クエリが与えられた順にそれぞれ 1 行ずつ出力せよ。

入力例 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