n villages numbered 0 to n - 1, joined by n - 1 two-way roads so that every village can be reached from every other one (the roads form a tree). Road roads[i] = [a, b] connects villages a and b. The array coins holds 1 for a village with a coin in it and 0 for one without.
A courier picks any village to start from. Then, as many times as they like, they either:
- collect every coin lying in a village at most two roads away from the current one, or
- drive along one road to a neighboring village.
The courier has to collect all the coins and come back to the starting village. Return the smallest number of road trips this takes; driving the same road several times counts every trip.coins=[1, 0, 0, 0, 0, 0, 1], roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] → 4
Start at village 2 and pick up the coin in village 0, two roads away. Drive to 3 and then to 4, which is close enough to grab the coin in 6. Drive back 4 → 3 → 2: 4 trips in total.
coins=[0, 1, 0, 1, 0], roads=[[0, 1], [0, 2], [0, 3], [3, 4]] → 0
From village 0 both coins (in 1 and in 3) are one road away, so no driving is needed.
coins=[0, 0, 0], roads=[[0, 1], [1, 2]] → 0
coins=[1, 0, 0, 0, 0, 0, 1], roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
4
Run checks the first 3 tests in your browser. Submit checks all 59 tests on the server, hidden ones included.