CF734E.Anton and Tree

Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.

There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).

To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). For example, consider the tree

and apply operation paint(3) to get the following:

Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.

安东正在他的花园里培育一棵树。如果你忘了，树是一种连通的无环无向图。

这棵树有 $n$ 个顶点，每个顶点被涂成黑色或白色。安东不喜欢多色的树，因此他希望修改这棵树，使得所有顶点颜色相同（全黑或全白）。

安东只能使用一种类型的操作来改变颜色。我们将其记为 $\text{paint}(v)$，其中 $v$ 是树中的某个顶点。该操作会改变所有满足以下条件的顶点 $u$ 的颜色：从 $v$ 到 $u$ 的最短路径上的所有顶点（包括 $v$ 和 $u$）颜色均相同。例如，考虑如下这棵树：

对它执行操作 $\text{paint}(3)$ 后，得到如下结果：

安东关心的是：为使所有顶点颜色一致，他最少需要执行多少次操作？

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers color__i (0 ≤ color__i ≤ 1) — colors of the vertices. color__i = 0 means that the i-th vertex is initially painted white, while color__i = 1 means it's initially painted black.

Then follow n - 1 line, each of them contains a pair of integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (u__i, v__i) are distinct, i.e. there are no multiple edges.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）——树中顶点的数量。

第二行包含 $n$ 个整数 $\text{color}_i$（$0 \leq \text{color}_i \leq 1$）——各顶点的颜色。若 $\text{color}_i = 0$，表示第 $i$ 个顶点初始为白色；若 $\text{color}_i = 1$，则表示其初始为黑色。

接下来的 $n-1$ 行中，每行包含一对整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）——表示由对应边所连接的两个顶点的下标。保证所有对 $(u_i, v_i)$ 均互不相同，即不存在重边。

Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.

输出一个整数——Anton 为使树的所有顶点变为黑色或所有顶点变为白色所需执行的最少操作次数。

In the first sample, the tree is the same as on the picture. If we first apply operation paint(3) and then apply paint(6), the tree will become completely black, so the answer is 2.

In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.

在第一个样例中，树与图中所示相同。如果我们先执行操作 paint(3)，再执行操作 paint(6)，则整棵树将变为全黑，因此答案为 2。

在第二个样例中，树初始即为白色，因此无需执行任何操作，答案为 0。