← 返回题目列表

Codeforces · 734/E

E. 安东和树

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

安东正在他的花园里种一棵树。如果您忘记了,树是一个连通的非循环无向图。

树中有n个顶点,每个顶点都被漆成黑色或白色。安东不喜欢五彩树,因此他想更改树,使所有顶点具有相同的颜色(黑色或白色)。

要更改颜色,Anton 只能使用一种类型的操作。我们将其表示为paint(v),其中v是树的某个顶点。此操作更改所有顶点 u 的颜色,使得从 v 到 u 的最短路径上的所有顶点具有相同的颜色(包括 v 和 u)。例如,考虑树

并应用操作paint(3)以获得以下结果:

Anton 感兴趣的是为了使所有顶点的颜色相等而需要执行的最少操作数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) - 树中的顶点数。

第二行包含 n 个整数 colori (0 ≤ colori ≤ 1) — 顶点的颜色。 colori = 0 意味着第 i 个顶点最初被漆成白色,而 colori = 1 意味着它最初被漆成黑色。

然后是 n - 1 行,每行包含一对整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由相应边连接的顶点的索引。保证所有对 (ui, vi) 都是不同的,即不存在多重边。

输出

打印一个整数 - Anton 必须应用的最少操作数才能使树的所有顶点变黑或使树的所有顶点变白。

示例

输入 #1

11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

输出 #1

2

输入 #2

4
0 0 0 0
1 2
2 3
3 4

输出 #2

0

注意

在第一个示例中,树与图片上的树相同。如果我们先应用paint(3)操作,然后再应用paint(6)操作,树将变成完全黑色,所以答案是2。

在第二个示例中,树已经是白色的,因此不需要应用任何操作,答案为 0。