28715번 - Деревянный замок 다국어

문제

Чтобы попасть в заброшенный дом, в котором прячется Оно, ребятам нужно открыть дверь с хитроумным замком. Этот замок представляет собой дерево из $n$ вершин, каждая из которых покрашена в белый или черный цвет. Чтобы открыть замок, нужно уничтожить все вершины этого дерева. Для этого ребята могут выполнять две операции:

1. Перекрасить еще не уничтоженную вершину из белого в черный, или из черного в белый.
2. Запустить цепную реакцию, уничтожающую группу связных вершин одного цвета. Формально, ребята могут выбрать любую еще не уничтоженную вершину цвета $c,ドル уничтожить ее и все вершины цвета $c,ドル достижимые из нее по еще не уничтоженным вершинам цвета $c$.

Разумеется, ребятам хочется поскорее попасть в дом, поэтому им интересно узнать, какое минимальное количество операций им потребуется, чтобы открыть замок.

입력

В первый строке дано целое число $n$ --- количество вершин в графе (1ドル \le n \le 200,000円$). В следующей строке дана строка $s$ длины $n$ из символов 0ドル$ и 1ドル$. Если $i$-й символ строки $s$ равен 0ドル,ドル то $i$-я вершина покрашена в белый цвет, иначе --- в черный. В следующих $n - 1$ строках дано по два целых числа $a_i$ и $b_i$ --- ребра дерева (1ドル \le a_i, b_i \le n$).

Гарантируется, что ребра образуют дерево.

출력

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

제한

힌트

В первом тесте замок можно открыть за два действия следующим образом:

1. Перекрасить вершину 1ドル$ в белый цвет.
2. Запустить цепную реакцию из вершины 1ドル,ドル она уничтожит все вершины.