n halls numbered 0 to n - 1; links[i] = [a, b] is a passage between halls a and b. Every hall has a gate, and the first time it is opened the value gates[i] applies: a positive value is a reward for whoever opens it, a negative value is a fee they pay to open it.
The explorer starts in hall 0 and the rival starts in hall rival. Every second both move to a neighbouring hall. The explorer chooses a route from hall 0 to some leaf (a hall other than 0 with exactly one neighbour) and stops once there. The rival walks the shortest route to hall 0 and stops there.
In every hall along the way, a traveller opens its gate:
- if the gate is already open, nothing happens;
- if both arrive in the hall in the same second, they split the value: the explorer's share is gates[i] / 2 rounded down (for example, 7 → 3 and -7 → -4).
The starting halls are opened at second 0. Return the explorer's best possible net income over all choices of leaf (it may be negative).links=[[0, 1], [0, 2], [2, 3], [2, 4]], rival=4, gates=[2, -6, 8, 10, -4] → 16
At second 0 the explorer opens gate 0 (+2) while the rival opens gate 4. At second 1 both reach node 2 and split its reward: +4. Then leaf 3 is the better finish: +10. Total 2 + 4 + 10 = 16. Heading to leaf 1 would give only 2 - 6 = -4.
links=[[0, 1], [1, 2]], rival=2, gates=[-4, 6, 20] → -1
The rival opens gate 2 at second 0 and reaches gate 1 at second 1, together with the explorer, who takes half of it, 3. Gate 2 is already open when the explorer arrives. Total -4 + 3 = -1.
links=[[1, 0]], rival=1, gates=[-2, 8] → -2
links forms a treelinks=[[0, 1], [0, 2], [2, 3], [2, 4]], rival=4, gates=[2, -6, 8, 10, -4]
16
Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.