分数: 1500 点
问题陈述
你有一棵树 N 顶点编号 1, 2, ..., N。的 i第一条边连接顶点 a_i 和顶点 b_i。
还给你一个字符串 S 长度 N 组成 0 和 1。的 i第一个字符 S 代表放置在Vertex上的棋子数量 i.
Snuke 将执行以下操作若干次:
- 选择两块之间的距离至少为 2,并通过以下方式使这些部分彼此更接近 1。更正式地说,选择两个顶点 u 和 v,每个都有一个或多个块,并考虑它们之间的最短路径。这里的路径必须至少包含两条边。然后,从 u 到路径上的相邻顶点,并从 v 到路径上的相邻顶点。
通过重复此操作,Snuke 希望所有棋子都位于同一顶点上。这可能吗? 如果答案是肯定的,还需要找到实现它所需的最少操作数。
约束
- 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), ..., (a_{N - 1}, b_{N - 1}) 形成一棵树。
输入
输入由标准输入按以下格式给出:
N
S
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
输出
如果不可能将所有碎片放在同一顶点上,则打印 -1。如果可能,请打印所需的最少操作数。
示例输入 1
7 0010101 1 2 2 3 1 4 4 5 1 6 6 7
示例输出 1
3
我们可以通过以下三个操作收集所有碎片:
- 选择顶点上的棋子 3 和 5.
- 选择顶点上的棋子 2 和 7.
- 选择顶点上的棋子 4 和 6.
示例输入 2
7 0010110 1 2 2 3 1 4 4 5 1 6 6 7
示例输出 2
-1
示例输入 3
2 01 1 2
示例输出 3
0