Collect Coins

Each vertex of an undirected tree holds 0 or 1 coin. You may choose any starting vertex; whenever you reach a vertex, you collect every coin within graph distance at most 2. You move along edges and must eventually return to the starting vertex. Find the minimum number of edges traversed to collect all the coins.

输入格式

The first line contains n, followed by n values of 0/1, followed by n−1 undirected 0-based edges, guaranteed to form a tree. The original gave no numeric bounds; this site adds 1≤n≤200000.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
1 0 0 0 0 1
0 1
1 2
2 3
3 4
4 5

输出：

2

样例 2

输入：

4
1 1 1 1
0 1
0 2
0 3

输出：

0

样例 3

输入：

1
1

输出：

0

样例说明

The outputs of the three public examples are, in order: 2; 0; 0. Verified by independent enumeration or direct simulation.