← 返回题目列表

AtCoder · agc034_e

E. 完整压缩

中文机器翻译题面 查看原题

分数: 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