QUESTION 3: DATA COLLECTION
There are n branches connected by n - 1 undirected edges, forming a tree.
Branches are numbered from 0 to n - 1.
You are given an array a:
a[i] = 1 means branch i contains data.
a[i] = 0 means branch i contains no data.
You can choose any branch as your starting point.
While standing at a branch, you can collect data from that branch and from every branch at most 2 edges away.
Collecting data costs nothing and does not require moving to the branch containing it.
You can move along any edge in either direction. Each time you cross an edge, the cost increases by 1. Crossing the same edge again also costs 1.
Find the minimum total cost needed to collect all the data and return to your starting branch.
INPUT
The first line contains n.
The second line contains n integers:
a[0], a[1], ..., a[n - 1].
Each of the next n - 1 lines contains two integers u and v, describing an edge between branches u and v.
CONSTRAINTS
2 <= n <= 100000
Each a[i] is either 0 or 1.
0 <= u, v < n
u != v
The edges form a tree.
OUTPUT
Print the minimum total number of edge crossings.
EXAMPLE 1
Input:
5
1 0 0 0 1
0 1
1 2
2 3
3 4
Output:
0
Explanation:
Start at branch 2.
Branches 0 and 4 are both 2 edges away.
Collect all data without moving.
EXAMPLE 2
Input:
6
1 0 0 0 0 1
0 1
1 2
2 3
3 4
4 5
Output:
2
Explanation:
Start at branch 2 and collect data from branch 0.
Move to branch 3 and collect data from branch 5.
Return to branch 2.
Route:
2 -> 3 -> 2
Total cost: 2.
EXAMPLE 3
Input:
11
0 0 1 1 0 0 0 0 0 1 1
0 1
0 2
0 6
1 3
1 4
3 10
4 5
6 7
7 8
8 9
Output:
6
Explanation:
One optimal route is:
1 -> 0 -> 6 -> 7 -> 6 -> 0 -> 1
At branch 1, collect data from branches 3 and 10.
At branch 0, collect data from branch 2.
At branch 7, collect data from branch 9.
The route crosses 6 edges and returns to its starting branch.