Anton and Tree
Contest: Codeforces Round 379 (Div. 2)
Difficulty rating: 2100
Tags: dfs and similar, dp, trees

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.

Input format:
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 colori (0 ≤ colori ≤ 1) — colors of the vertices. colori = 0 means that the i-th vertex is initially painted white, while colori = 1 means it's initially painted black.

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

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
2

Example input:
4
0 0 0 0
1 2
2 3
3 4

Example output:
0

Editorial:
At first, let's observe that if we unite some two vertices connected by an edge, that are the same color, in one vertex, the answer will not change. Let's do this. Then, for instance, the tree
will look in this way:
We'll also do such tree "compression" after every painting operation. Then, for instance, the tree
will change after paint(2) operation and the tree "compression" in this way:
It's obvious that the tree will be painted in one color if and only if, when after such painting operations with the "compression" only one vertex remains.
Let's call the tree diameter maximal possible shortest path between two vertices of the tree. It's not hard to observe that the tree will be painted in one color if and only if, when the tree diameter becomes equal to 0, because the diameter is 0 only in the tree with one vertex.
Then, we'll see the following fact: the tree diameter can't be decreased more than by two per one painting operation with the "compression". So the answer cannot be less than $${ \frac { d + 1 } { 2 } }$$, where d is the tree diameter.
Now, we'll prove that it's always possible to paint the tree in $${ \frac { d + 1 } { 2 } }$$ operations. Find such vertex that the shortest path from it to any other vertex doesn't exceed $${ \frac { d + 1 } { 2 } }$$. Such vertex can always be found, because otherwise the tree diameter won't be less that d + 1, which is impossible. Now see that if we paint this vertex $${ \frac { d + 1 } { 2 } }$$ times, we will paint the tree in one color.
Time complexity is $${\mathcal{O}}(n)$$.