配点 : $1500$ 点

問題文

頂点に番号 $1, 2, ..., N$ がついた $N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。 また長さ $N$ の 0, 1 からなる文字列 $S$ が与えられ、$S$ の $i$ 文字目は頂点 $i$ に置いてあるコマの個数を表しています。

すぬけ君は、以下の操作を好きなだけ行います。

• 距離が $2$ 以上離れたコマ $2$ 個を選び、お互いに $1$ ずつ近づける。 正確に述べると、コマの置かれた頂点 $u, v$ を選び、$u, v$ 間の最短パスを考える。ここでパスの辺数が $2$ 以上となるように選ぶことにする。パスにおいて $u$ に隣り合う頂点にコマを $1$ 個 $u$ から動かし、$v$ に隣り合う頂点にコマを $1$ 個 $v$ から動かす。

すぬけ君はこれを繰り返し、すべてのコマを同じ頂点に集めたいです。このようなことは可能でしょうか？ 可能な場合、それを達成するのに必要な操作の最小回数も求めてください。

制約

• $2 \leq N \leq 2000$
• $|S| = N$
• $S$ は 0, 1からなり、また少なくとも $1$ 文字は 1 を含む
• $1 \leq a_i, b_i \leq N(a_i \neq b_i)$
• 辺 $(a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1})$ は木をなす

入力

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

$N$

$S$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_{N - 1}$ $b_{N - 1}$

出力

コマを同じ頂点に集められない場合 -1、集められる場合は操作の最小回数を出力せよ。

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7

3

• 頂点 $3, 5$ のコマを選ぶ
• 頂点 $2, 7$ のコマを選ぶ
• 頂点 $4, 6$ のコマを選ぶ

の $3$ 回の操作ですべてのコマを頂点 $1$ に集めることができます。

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7

-1

2
01
1 2

0