AT_agc034_e [AGC034E] Complete Compress

给定一棵有 $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`；如果可以，输出所需的最小操作次数。

## 限制条件 - $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 翻译