E： ブロッコリー？カリフラワー？ (Broccoli or Cauliflower)
問題（物語）
あなたはみんなに料理を振る舞うことになり、得意料理の100%ハンバーグを作ることにした。このハンバーグは合挽き肉を使用していないため、いつも周りから好評なハンバーグである（100%牛肉とは言っていない）。ハンバーグといえば付け合わせの野菜も必要である。そこであなたは付け合わせに茹でたブロッコリーをつけようとし、買い物に行くことにした。 スーパーの野菜コーナーにはブロッコリーによく似た野菜が共に置かれていた。そう、カリフラワーである。しかもこのスーパーはブロッコリーとカリフラワーを同じ場所に混ぜておいているため、商品の置き場所ではブロッコリーかカリフラワーかは判断できない。このスーパーでブロッコリーかカリフラワーかを見分ける方法はただ一つで、それぞれの蕾の色が緑の蕾が多いならばブロッコリー、白の蕾が多いならばカリフラワーである。しかし、蕾の数は膨大で、数えるのは大変だ。その上、ここの野菜は厄介で、たまに蕾の色が緑から白、白から緑に入れ替わることがある。これにより、今までブロッコリーだった野菜がカリフラワーに変わったりする場合がある。そこでプログラミングが得意なあなたは蕾の色が入れ替わるたびにその野菜がブロッコリーになったか、カリフラワーになったかを見分けるプログラムを書くことにした。
↓小さいツブツブ1つ1つが蕾です。
問題
n 頂点からなる根つき木 T が与えられる。ここで、 n は奇数であり、 T の根は頂点番号が 1 である。 さらに、それぞれの頂点 v に対して G もしくは W のラベルが与えられ、頂点 v と v の子孫からなる部分木を v の部分木 T_v と呼ぶ。
次の操作が q 回行われる。それぞれの操作終了時に、 T 中の全ての頂点で、G のラベルを持つ頂点が過半数をこえる場合は “broccoli”、そうでない場合は “cauliflower” と出力せよ。
- 頂点 v が与えられる。部分木 T_v 中の頂点 u がラベル G を持つならば u のラベルを W に、W を持つならば u のラベルを G にする。
入力形式
入力は次のように与えられる。
n q p_2 ... p_n c_1 ... c_n v_1 $\vdots$ v_q
1行目は木の頂点数 n とクエリ数 q が与えられる。ここで、 n は奇数である。
2行目は頂点 2 から n それぞれに対する親が与えられる。
3行目はそれぞれの頂点のラベル c_i が与えられる。
最後に、i + 3 行目には i 回目の操作を行う頂点 v_i が与えられる。
制約
- 1 \leq n \leq 100,000、ただし n は奇数である。
- 1 \leq q \leq 100,000
- 1 \leq p_i < i（2 \leq i \leq n）
- c_j は G もしくは W である。（1 \leq j \leq n）
- 1 \leq v_i \leq n（1 \leq i \leq q）
出力形式
出力は q 行からなり、各行には “broccoli” もしくは “cauliflower” を出力せよ。
入力例1
7 4 1 1 2 2 3 3 G G W W W G G 2 1 3 4
出力例1
broccoli cauliflower cauliflower broccoli
入力例2
17 18 1 1 1 3 1 4 2 4 3 6 10 9 3 4 5 15 W W W W W W W W G W G G W G W W W 6 7 1 9 14 6 4 5 3 7 8 13 9 6 14 12 9 13
出力例2
cauliflower cauliflower broccoli broccoli broccoli broccoli broccoli broccoli broccoli cauliflower cauliflower cauliflower cauliflower cauliflower broccoli cauliflower cauliflower cauliflower