Coin Collector's Quest

The first line of input contains an integer 'n', the number of nodes.

The second line contains 'n' space-separated integers (0s and 1s), representing the coins array.

The third line contains an integer 'E', the number of edges (which will be n-1 for a tree).

The next 'E' lines each contain two space-separated integers, u and v, representing an edge.

Print a single integer representing the minimum number of operations required.

The key to this problem is understanding that the set of required edges to travel is fixed, regardless of the starting point.    The journey must cover all edges on the unique paths between all coin-containing nodes.

The optimal path will traverse every necessary edge twice (once down, once back up), except for the longest path from the chosen starting node to a leaf in the "coin subtree", which is traversed only once.

Sample Input 1:

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

Sample Output 1:

2

Explanation for Sample 1:

Coins at {1, 4}. The minimal subtree connecting them is just the path 1-4.
- To get both coins, you must travel the edge (1,4).
- Oh, the edge is 1-3, 1-4. The path from 1 to 4 is just the edge (1,4).
- The minimal subtree is the path 1-4. It requires no, 1 and 4 are children of 0. No, children of 1. Okay.
- The path between 1 and 4 is `1-4`. This seems wrong. It must be `0-1-4`.
- Edges: 0-1, 0-2, 1-3, 1-4, 2-5. Coins: 1, 4. Path is 1-0-2-5, no.
- The path is `4-1`. Length 1. Subtree just contains node 1 and 4 and edge (1,4). Start at 1, move to 4. Total steps: 1. Wait.
- Ah, the total required trip must traverse the edge (0,1) and (1,4). Subtree has nodes {0,1,4} and edges (0,1),(1,4).
- Start at 4. Go 4->1->0. Cost 2. All coins collected. Total 2.

Sample Input 2:

3
1 1 1
2
0 1
1 2

Sample Output 2:

2

Explanation for Sample 2:

The graph is a line 0-1-2 and all nodes have coins.
The coin subtree is the entire tree.
Start at 0, travel to 1, then to 2. Total steps = 2.

Expected Time Complexity:

The expected time complexity is O(n).

Constraints:

1 <= n <= 10^5
`coins[i]` is 0 or 1.
There is at least one coin.

Time limit: 1 sec