| Codeforces Round 379 (Div. 2) |
|---|
| Закончено |
Антон посадил в своём саду дерево. Напоминаем, что дерево — это связный неориентированный граф, не содержащий циклов.
Вскоре дерево выросло. Каждая из его 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.
