Equalize Adjacent Node Stones on a Tree

Problem A tree of n nodes has some number of stones on each node (possibly zero). You may only add stones, never remove them. Add the minimum total number of extra stones so that for every edge (u, v), |stones[u] - stones[v]| == 1.

Input / Output

• Input: n, the tree's n-1 edges, and an array stones of non-negative initial counts.
• Output: a single integer — the minimum total number of stones added.

Constraints

• The input is a tree: connected, n nodes, n-1 edges, no cycles.
• Initial counts are non-negative; the final count at every node must be >= its initial count, since removal is forbidden.
• The required difference is exactly 1 on every edge, not at most 1.

Example

• Path of 3 nodes with stones [0,0,0] → final [0,1,0] costs 1 → answer 1.
• Path of 3 nodes with stones [5,0,5] → setting the centre to 4 lets both leaves stay at 5, costing 4; pushing the centre to 6 would cost 6. The cheaper option makes the centre a valley, not a peak — which is why a "raise everything to satisfy the parent" greedy is wrong.