n towns numbered 0 to n − 1, connected by roads into a tree: roads[i] = [a, b] is a road between towns a and b. Visiting town i costs cost[i].
You must make the trips listed in trips: trips[i] = [start, end] is a trip from start to end. A trip costs the sum of the prices of all towns on its path, including both ends.
Before the first trip you may pick some towns, **no two of which are joined by a road**, and halve their prices. Return the smallest possible total cost of all trips.n=3, roads=[[0, 1], [1, 2]], cost=[4, 6, 8], trips=[[0, 2]] → 12
The trip passes all three towns. Towns 0 and 2 are not neighbors, so both can get the discount: 2 + 6 + 4 = 12. Discounting only town 1 would give 4 + 3 + 8 = 15.
n=4, roads=[[0, 1], [0, 2], [0, 3]], cost=[10, 2, 2, 2], trips=[[1, 2], [2, 3], [3, 1]] → 27
Every trip goes through the hub 0, which is visited three times. Discounting the hub gives 3 · 5 + 2 · (2 + 2 + 2) = 27, while discounting the three outer towns instead gives 36.
n=1, roads=[], cost=[6], trips=[[0, 0], [0, 0]] → 6
n=3, roads=[[0, 1], [1, 2]], cost=[4, 6, 8], trips=[[0, 2]]
12
Run checks the first 3 tests in your browser. Submit checks all 49 tests on the server, hidden ones included.