n nodes numbered 0 to n − 1, rooted at node 0; edges[i] = [a, b] is an edge between a and b. Node i holds coins[i] coins. You are also given a number toll.
You must collect the coins at **every** node, and a node can be collected only after all of its ancestors have been. Each node is collected in one of two ways:
- **toll**: you earn coins[i] − toll points (this may be negative);
- **half**: you earn ⌊coins[i] / 2⌋ points, but afterwards every node in the subtree of i has its coins halved, rounding down.
Return the largest total number of points.edges=[[0, 1], [0, 2], [2, 3]], coins=[6, 1, 12, 9], toll=4 → 15
Node 0 pays the toll: 6 − 4 = 2. Node 1 is halved: 0 (the toll would give −3). Node 2 pays the toll: 12 − 4 = 8. Node 3 pays the toll: 9 − 4 = 5. Total 15.
edges=[[1, 0], [1, 2]], coins=[0, 8, 8], toll=3 → 7
Halving the root 0 gives 0 instead of −3, but nodes 1 and 2 drop to 4 coins each and yield only 2 + 2 = 4. Paying the toll at the root (−3) and at both children (5 + 5) is better: 7 in total.
edges=[[0, 1], [0, 2], [2, 3]], coins=[6, 1, 12, 9], toll=4
15
Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.