問題一覧 > 通常問題

No.2205 Lights Out on Christmas Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 88
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 seekworserseekworser
2 ProblemId : 9096 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-02 21:32:16

問題文

$1$から$N$までの番号がついた$N$個の頂点からなる木が与えられます。$i$番目の辺は頂点$a_i$と頂点$b_i$を結んでいます。
また、各頂点は白か黒のいずれかの色で塗られており、頂点$i$の色は$c_i$です。ただし、$c_i=0$は白を、$c_i=1$は黒を表します。
あなたは以下の操作を0回以上何度でも行えます。全ての頂点の色を黒にすることができるか判定し、可能な場合は必要な操作回数の最小値を求めてください。

(操作)
$1\leq i \leq N-1$を満たす$i$を一つ選び、頂点$a_i$と頂点$b_i$の色をそれぞれ反転させる。すなわち、頂点の色が黒ならば白に、白ならば黒に変える。

入力

$N$
$a_1~b_1$
$\vdots$
$a_{N-1}~b_{N-1}$
$c_1~\cdots~c_N$

入力は全て整数で以下の制約を満たす。

  • $2\leq N \leq 2\times 10^5$
  • $1\leq a_i < b_i \leq N$
  • $i\neq j$ならば$(a_i, b_i)\neq(a_j, b_j)$
  • $c_i$は0または1

出力

全ての頂点の色を黒にするために必要な操作回数の最小値を出力してください。
ただし、何度操作を行なっても全ての頂点の色を黒にできないならば-1を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
1 2
2 3
0 1 0
出力
2

まず辺1に対して操作を行い、その後、辺2に対して操作を行います。すると、各頂点の色は$(0, 1, 0)\to(1, 0, 0)\to(1, 1, 1)$と変化します。
1回以下の操作で全ての頂点の色を黒にすることはできないので2が答えです。

サンプル2
入力
3
1 2
2 3
1 0 1
出力
-1

何度操作を行なっても全ての頂点の色を黒にすることはできません。

サンプル3
入力
10
1 4
3 5
5 9
8 10
5 7
1 3
4 10
2 9
6 9
1 0 0 0 1 0 0 0 1 1
出力
6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。