Equalize Root-to-Leaf Sums in an N-ary Tree

You are given a rooted tree. Node i has nonnegative value values[i]. In one operation, you may increase one node's value by 1.

Return the minimum number of operations needed to make the sum of node values along every root-to-leaf path equal.

The tree is represented by a parent array: node 0 is the root, parents[0] == -1, and for every other node parents[i] is its parent.

Function Contract

def min_path_sum_increments(values: list[int], parents: list[int]) -> int:
    ...

Constraints

• 1 <= len(values) == len(parents) <= 200_000
• 0 <= values[i] <= 10**9
• parents[0] == -1
• For i > 0, 0 <= parents[i] < len(values).
• The parent array describes one valid rooted tree.
• A node may have any number of children.
• Your implementation must handle a tree deeper than Python's default recursion limit.

Example

values = [2, 3, 4]
parents = [-1, 0, 0]
result = 1

Increasing the value of node 1 once makes both root-to-leaf sums equal.

Equalize Root-to-Leaf Sums in an N-ary Tree

Implement min_path_sum_increments(values, parents). Node zero is the root, parents[0] is -1, and the parent array describes one rooted tree. One operation increases one nonnegative node value by one. Return the exact minimum operation count as a canonical nonnegative decimal string. The string result remains exact even when the count exceeds signed 64-bit range. The implementation must support trees deeper than the language's default recursion limit.

Hints

1. Process children before their parent with an explicit-stack postorder.
2. For each child subtree, keep its already-equal root-to-leaf sum and accumulate the operation count with arbitrary-precision or decimal arithmetic.
3. Sibling subtree sums must all be raised to their maximum; increasing a child root raises every path in that child subtree together.

Approach

Build children lists and an iterative traversal order, then process that order backward. A leaf's subtree path sum is its value. At an internal node, each child subtree is already internally equalized. All child sums must reach their maximum; adding the difference to each lower child's root is both sufficient and minimal because it raises every path in that subtree at once. Accumulate those differences exactly with arbitrary-precision or decimal addition, propagate nodeValue+maximum upward, and return the final count's canonical decimal spelling.

• Time complexity: O(n * d), where d is the number of decimal digits in the exact operation count.
• Space complexity: O(n + d) for tree state and the exact decimal accumulator.