H - 白黒ツリー
Editorial
/
Time Limit: 5 sec / Memory Limit: 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