Uber Circular Shuttle Optimization

Choose any start on the tree. When you pass a station, you can pick up, for free, all passengers at most 2 edges away from that station. Traversing an edge costs 1; you must pick up every passenger and return to the start. Find the minimum number of moves.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n, the second line contains n values of 0/1 indicating passengers, followed by n−1 lines of tree edges (0-based). 1≤n≤30000.

输出格式

Output one integer answer.

样例 1

输入：

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

输出：

2

样例 2

输入：

8
0 0 0 1 1 0 0 1
0 1
0 2
1 3
1 4
2 5
5 6
5 7

输出：

2

样例 3

输入：

1
1

输出：

0

样例说明

Example 1: going back and forth between the two middle stations of the chain covers both ends, at a cost of 2. Example 2: going back and forth between 0 and 2 covers 3, 4, and 7, at a cost of 2. Example 3: the start is the only station, so no moves are needed.