Svjetlo

Time limit2sMemory limit512 MB

Summary

Given a tree of bulbs with their initial on/off states, find the shortest walk along wires that visits each off bulb an odd number of times and each on bulb an even number of times.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming
Solved: No attempts yet

Problem

Oh no! It is nighttime, and little Fabijan is afraid of the dark. To make things worse, the chandelier in his room is broken.

The chandelier is made up of $n$ light bulbs connected by $n-1$ wires, so that each wire connects two bulbs and all bulbs are connected, either directly or through other bulbs. In other words, the chandelier is a tree.

Each bulb has a button that changes its state. If the bulb is turned off, pressing the button turns it on, and if it is on, it turns it off. In the beginning, some bulbs are on and some are off (it is possible that all are turned off). All $n$ bulbs need to be turned on in order for Fabijan to stop being afraid, since only then will there be enough light in the room.

Fabijan will choose some sequence of bulbs such that bulbs that are consecutive in the sequence are directly connected by some wire. Bulbs can be repeated. He will then go around the bulbs in the order they appear in the sequence. Since Fabijan really likes pressing buttons, whether on light bulbs, washing machines, or in elevators, each time he visits a bulb he presses its button once, changing its state.

Help Fabijan and determine the length of the shortest sequence of bulbs such that in the end all bulbs are turned on. There will be at least one bulb that is turned off in the beginning.

Input

The first line contains an integer $n$ , the number of light bulbs. Bulbs are labeled by integers from $1$ to $n$ .

The second line contains a string of $n$ characters '0' and '1'. If the $i$ -th character is '0', then in the beginning the $i$ -th bulb is turned off, and if it is '1', it is turned on.

Each of the following $n-1$ lines contains two integers $x$ and $y$ ( $1 \le x, y \le n$ ), the labels of two bulbs that are directly connected by a wire.

Output

Output the minimum possible length of a sequence such that all bulbs are turned on in the end.

It can be proven that such a sequence always exists.

Constraints

In all subtasks it holds that $2 \le n \le 500\,000$ .

Hint

Clarification of the first example:

Fabijan can choose the sequence 1, 2, 3, 2.

Examples3

Example 1
Input
```
3
010
1 2
2 3
```
Expected output
```
4
```
Example 2
Input
```
5
00000
1 2
2 3
2 4
3 5
```
Expected output
```
7
```
Example 3
Input
```
5
00100
1 2
2 3
2 4
3 5
```
Expected output
```
8
```