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.