Given a rooted tree with edge costs, increase edge costs so every root-to-leaf path has the same total cost using the minimum number of increments.
Minimum Increments To Equalize Leaf Paths
You are given a rooted tree with n nodes labeled from 0 to n - 1. The root is node 0. Each non-root node has exactly one parent, and the edge from a node to its parent has a positive integer cost.
You may increase the cost of any edge by any non-negative integer amount. Your goal is to make all root-to-leaf path sums equal, while minimizing the total amount of increase applied across all edges.
Return the minimum total increment needed.
A root-to-leaf path sum is the sum of edge costs along the path from the root to a leaf node.
Intuition
The tree can be processed bottom-up: each subtree can report the maximum path sum needed beneath it, and smaller child paths can be raised to match that maximum.
Input Format
- An integer
n, the number of nodes. - A list of
n - 1parent-cost relations for nodes1..n-1, where each relation gives the parent of the node and the edge cost to that node.
You may assume the input describes a valid rooted tree with root 0.
Output Format
- Return a single integer: the minimum total increment required so all root-to-leaf path sums become equal.
Constraints
1 <= n- The input forms a valid rooted tree.
- Edge costs are positive integers.
- You may increase edge costs by any non-negative integers.
- The answer fits in a 64-bit signed integer.
Example 1
Input
n = 5 parents = [0, 0, 1, 1] costs = [3, 1, 2, 4]
Output
2
Explanation
The tree has edges 0->1 (3), 0->2 (1), 1->3 (2), and 1->4 (4).
Root-to-leaf sums are:
- 0->2 = 1
- 0->1->3 = 5
- 0->1->4 = 7
Raise the edge 0->2 by 6? That would be too much if done alone. Instead, equalize bottom-up:
- At node 1, child path sums are 2 and 4, so increase the smaller by 2.
- Now node 1 contributes 6 to the root.
- At the root, child path sums are 3 + 6 = 9 through node 1 and 1 through node 2, so increase the edge to node 2 by 8.
Total increase is 2 + 8 = 10.
This illustrative example shows the bottom-up equalization idea.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.