小さな木の塗り分け Python2編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
頂点数 n の木が与えられます。
すでに、根以外のすべての頂点が赤または青に塗られています。
根の頂点を赤または青に塗り分ける方法のうち、以下の条件を満たすものが何通り存在するか求めてください。(答えは 0, 1, 2 のいずれかになります。)
・ 任意の連続する長さ 1 以上のパスについて、必ず (そのパスに含まれる赤に塗られた頂点の個数) <= (そのパスに含まれる青に塗られた頂点の個数) が成り立つ。
根の深さを 0 としたとき、与えられる木は深さ 2 以下であることが保証されています。
- 入力される値
-
n
c_1 c_2 ... c_n
a_1 b_1
a_2 b_2
...
a_{n-1} b_{n-1}
・ 1 行目に、木の頂点数を表す整数 n が与えられます。
・ 2 行目に、i 番目の頂点が根なら c_i = 0, 赤なら c_i = 1, 青なら c_i = 2 であるような整数列 c_1, c_2, ..., c_n が半角スペース区切りで与えられます。
・ 続く n-1 行に、整数 a_i, b_i が半角スペース区切りで与えられます。これは、a_i 番目の頂点と b_i 番目の頂点が辺で結ばれていることを表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 10000 = 10^4
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ n-1)
・ 0 ≦ c_i ≦ 2 (1 ≦ i ≦ n-1)
・ a_i ≠ b_i (1 ≦ i ≦ n-1)
・ (a_i, b_i) ≠ (a_j, b_j) かつ (b_i, a_j) ≠ (a_j, b_j) (1 ≦ i, j ≦ n-1, i ≠ j)
・ 与えられるグラフは木であり、その深さは 2 以下である
・ c_i = 0 となる i がちょうど 1 つ存在する
- 入力例1
-
4
0 2 2 2
1 2
1 3
3 4
- 出力例1
-
2
- 入力例2
-
4
0 2 2 1
1 2
1 3
3 4
- 出力例2
-
1
