Equalize Root-to-Leaf Sums in an N-ary Tree
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# 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
```python
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
```text
values = [2, 3, 4]
parents = [-1, 0, 0]
result = 1
```
Increasing the value of node `1` once makes both root-to-leaf sums equal.
Overview: Find the minimum total increments needed to make every root-to-leaf path in a nonnegative-valued N-ary tree have the same sum. The parent-array input may contain 200,000 nodes and a depth beyond Python's recursion limit.
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.
Constraints
- 1 <= len(values) == len(parents) <= 200,000
- 0 <= values[i] <= 10^9
- parents[0] == -1 and the parent array describes one valid rooted tree.
- A node may have any number of children.
- Use an iterative traversal so very deep trees are supported.
- Return the exact count as a canonical decimal string with no leading zeroes.
Examples
Input: ([5], [-1])
Expected Output: "0"
Explanation: One root-to-leaf path is already equal to itself.
Input: ([2, 3, 4], [-1, 0, 0])
Expected Output: "1"
Explanation: Raise the lower child by one.
Hints
- Process children before their parent with an explicit-stack postorder.
- For each child subtree, keep its already-equal root-to-leaf sum and accumulate the operation count with arbitrary-precision or decimal arithmetic.
- Sibling subtree sums must all be raised to their maximum; increasing a child root raises every path in that child subtree together.