E. Антон и дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон посадил в своём саду дерево. Напоминаем, что дерево — это связный неориентированный граф, не содержащий циклов.

Вскоре дерево выросло. Каждая из его n вершин оказалась покрашена либо в чёрный, либо в белый цвет. Однако, Антону не нравятся разноцветные деревья, и поэтому он решил покрасить дерево так, чтобы оно было либо полностью белым, либо полностью чёрным.

Для изменения цвета вершин дерева Антону доступна только одна операция, обозначим её как paint(v), где v — некоторая вершина дерева. Эта операция перекрашивает в противоположный цвет все такие вершины u, что на кратчайшем пути от u до v все вершины покрашены в один цвет (при этом сами вершины u и v также учитываются). Например, дерево

после применения операции paint(3) станет следующим:

Антону стало интересно, за какое минимальное количество операций покраски ему удастся сделать так, чтобы дерево стало покрашено в один цвет. Помогите ему найти это число!

Входные данные

В первой строке входных данных находится одно целое число n (1 ≤ n ≤ 200 000) — количество вершин в дереве.

Во второй строке входных данных находятся n целых чисел colori (0 ≤ colori ≤ 1) — цвета вершин. Если colori = 0, это значит, что i-я вершина покрашена в белый цвет, если colori = 1, это значит, что i-я вершина покрашена в чёрный цвет.

В каждой из следующих n - 1 строк входных данных находится пара целых чисел ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — рёбра дерева. Гарантируется, что все пары (ui, vi) различны, то есть граф не содержит кратных рёбер.

Выходные данные

В единственной строке выходных данных выведите единственное число — минимальное количество операций покраски, которое необходимо Антону, чтобы дерево стало либо полностью белым, либо полностью черным.

Примеры
Входные данные
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
Выходные данные
2
Входные данные
4
0 0 0 0
1 2
2 3
3 4
Выходные данные
0
Примечание

В первом примере дерево такое же, как и на рисунке в условии. Если применить к нему сначала операцию paint(3), потом операцию paint(6), то оно будет полностью покрашено в черный цвет, поэтому ответ — 2.

Во втором примере дерево уже и так полностью покрашено в белый цвет, и к нему не придется применять ни одной операции покраски, поэтому ответ — 0.