题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1, 2, \ldots, N$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。另外，给定一个长度为 $N$ 只包含 0 和 1 的字符串 $S$，$S$ 的第 $i$ 个字符表示在顶点 $i$ 上放置的棋子数量。

すぬけ君可以进行如下操作任意次：

• 选择距离至少为 $2$ 的两个棋子，将它们各自向对方靠近一步。具体来说，选择放有棋子的顶点 $u$ 和 $v$，考虑 $u$ 到 $v$ 的最短路径，要求该路径的边数至少为 $2$。然后，将 $u$ 上的一个棋子移动到与 $u$ 相邻的顶点，将 $v$ 上的一个棋子移动到与 $v$ 相邻的顶点。

すぬけ君希望通过若干次操作，将所有棋子集中到同一个顶点。请判断是否可能做到。如果可能，请输出所需的最小操作次数。

输入格式

输入通过标准输入给出，格式如下：

$N$

$S$

$a_1$ $b_1$

$a_2$ $b_2$

$\ldots$

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

输出格式

如果无法将所有棋子集中到同一个顶点，输出 -1；如果可以，输出所需的最小操作次数。

样例 1

输入

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

输出

3

样例 2

输入

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

输出

-1

样例 3

输入

2
01
1 2

输出

0

说明/提示

限制条件

• $2 \leq N \leq 2000$。
• $|S| = N$。
• $S$ 只包含 0 和 1，且至少有一个字符为 1。
• $1 \leq a_i, b_i \leq N$，且 $a_i \neq b_i$。
• 边 $(a_1, b_1), (a_2, b_2), \ldots, (a_{N-1}, b_{N-1})$ 构成一棵树。

样例说明 1

• 选择顶点 $3, 5$ 上的棋子。
• 选择顶点 $2, 7$ 上的棋子。
• 选择顶点 $4, 6$ 上的棋子。

通过 $3$ 次操作，可以将所有棋子集中到顶点 $1$。

由 ChatGPT 4.1 翻译