PEG Judge - WC16 #4 - Hopps and Wilde on the Case

Woburn Challenge 2016-17 Round 4 - Senior Division

Problem 4: Hopps and Wilde on the Case

"Hopps, Wilde… parking duty. Dismissed."
"Just kidding! We have reports of a street racer tearing up Savannah Central. Find him. Shut him down."

Nick has ended up joining the ZPD as Zootopia's first fox cop, and as Judy's partner, no less! They've been assigned a case to track down a dangerous street racing criminal, but it won't be easy – they'll need to do some investigative work before they can begin to assemble a list of suspects.

Zootopia has N (2 ≤ N ≤ 200) key locations, with N − 1 roads running amongst them. The i-th road runs between distinct locations A_i and B_i (1 ≤ A_i, B_i ≤ N), and can be traveled along in either direction in 1 minute. It's possible to reach every location from every other location by following a sequence of roads.

The ZPD headquarters are located in location 1, and aside from that, some other locations may be of significance to the investigation. For each location i, if C_i = 1, then Judy and Nick believe that it contains a clue, and will need to go check it out. Otherwise, if C_i = 0, then the location is of no interest to them. At least one location besides location 1 is guaranteed to contain a clue.

Judy and Nick will both start at the ZPD headquarters, and will then split up to each travel around Zootopia, inspecting all of the locations that contain clues. On the way, each of them may travel through any locations as many times as they'd like, and they may both be present in the same location at the same time. They've agreed to meet back at the headquarters once they're done. What's the minimum amount of time in which Judy and Nick can independently travel around by following sequences of roads, such that they both end up back at the ZPD headquarters, and such that every location with a clue ends up being visited by at least one of the two cops?

In test cases worth 10/36 of the points, N ≤ 15 and C_i = 1 for each i.
In test cases worth another 10/36 of the points, N ≤ 50 and C_i = 1 for each i.
In test cases worth another 8/36 of the points, C_i = 1 for each i.

Input Format

The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of a single integer C_i (for i = 1..N).
N − 1 lines follow, the i-th of which consists of two space-separated integers A_i and B_i (for i = 1..N − 1).

Output Format

Output one line consisting of a single integer – the minimum number of minutes required for Judy and Nick to visit all locations with clues (between the two of them) and both return to the ZPD headquarters.