Collect Opportunity Data in a Tree

You may start from any tree node; visiting a node collects all data within at most 2 edges of it. Find the minimum number of edge traversals needed to collect all data and return to the starting node. The source example with n=11 has only 9 edges and an isolated node 5, so it is not a valid tree; this site replaces it with a valid example.

输入格式

The first line contains n, the second line contains n data flags, each 0/1, followed by n−1 lines of edges u v. 2≤n≤100000, 0≤u,v<n, and the input is guaranteed to be a valid undirected tree.

输出格式

Output the minimum number of edge traversals; output 0 when there is no data or no movement is needed.

样例 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

输入：

2
0 0
0 1

输出：

0

样例说明

For a chain of length 6 with data at both ends, traversing the core edge twice suffices, so the answer is 2; a star tree and a tree with no data both give 0.