题目描述

頂点に番号 $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$ から動かす。

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

输入格式

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

$N$ $S$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_{N\ -\ 1}$ $b_{N\ -\ 1}$

输出格式

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

题目大意

给你一颗 $n$ 个节点的树，并用二进制串告诉你哪些节点上有棋子（恰好一颗）。

可以进行若干次操作，每次操作可以将两颗距离至少为 $2$ 的棋子向中间移动一步。

问能否通过若干次操作使得所有的棋子都在一个点上，如果能，输出最小操作次数，如果不能，输出 $-1$ 。

数据范围：$2 \leq n\leq 2000$。

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

3

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

-1

2
01
1 2

0

提示

制約

• $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}) $ は木をなす

Sample Explanation 1

- 頂点 $3,\ 5$ のコマを選ぶ - 頂点 $2,\ 7$ のコマを選ぶ - 頂点 $4,\ 6$ のコマを選ぶ の $3$ 回の操作ですべてのコマを頂点 $1$ に集めることができます。