Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Tree, Depth-First Search

Solution

LeetCode 3593 - Minimum Increments to Equalize Leaf Paths

Problem Understanding

We are given a rooted tree with root node 0. Every node has a cost, and the score of a root-to-leaf path is the sum of the costs of all nodes along that path.

We are allowed to increase the cost of any nodes by any non-negative amount. The amount of increase does not matter directly. Instead, the objective is to minimize the number of distinct nodes whose costs are modified.

The goal is to make every root-to-leaf path have exactly the same score.

A key observation is that increasing the cost of a node affects every root-to-leaf path passing through that node. Therefore, increasing an internal node can simultaneously adjust many leaf paths, potentially reducing the number of modified nodes compared to increasing leaves individually.

The input consists of:

n, the number of nodes.
edges, describing an undirected tree.
cost[i], the cost associated with node i.

The output is the minimum number of nodes whose costs must be increased so that all root-to-leaf path scores become equal.

The constraints are large:

Up to 10^5 nodes.
Node costs up to 10^9.

These constraints immediately rule out any solution that repeatedly recomputes path sums or explores many possible increment distributions. We need a linear or near-linear solution.

Several edge cases are important:

A tree containing only one leaf path already satisfies the requirement, so the answer is 0.
A node may have only one child. Such nodes do not create any balancing decisions because there is only one subtree path.
Multiple leaves may already have equal path sums.
The optimal solution may increase an internal node instead of several descendants, because one modification can affect many paths simultaneously.
Costs are very large, so only comparisons and additions should be performed. We must avoid algorithms whose complexity depends on cost values.

Approaches

Brute Force

A brute-force perspective is to first compute all root-to-leaf path sums and determine the target value, which must be at least the maximum path sum.

Then we could try all possible ways of distributing the required deficits across nodes. Whenever a path is too short, we must decide which nodes along that path should receive increments.

This approach quickly becomes infeasible because increments applied to internal nodes affect multiple paths simultaneously. The number of possible distributions grows exponentially with the tree size.

Even restricting ourselves to the maximum path sum as the final target does not help much. We would still need to explore an enormous number of choices regarding where deficits are assigned.

Key Insight

Instead of thinking globally about path sums, we can solve the problem bottom-up.

Consider any node u.

Suppose each child subtree has already been processed so that all root-to-leaf paths inside that subtree have equal scores.

For each child, we can compute:

The common score from that child down to its leaves.
The minimum number of modified nodes required to achieve that score.

Now the only remaining issue is making all child subtrees contribute the same score when viewed from node u.

Let:

mx be the largest child score.

Every child with a smaller score must gain exactly:

mx - child_score

additional value.

The crucial observation is that whenever a child subtree is short by some positive amount, the cheapest way is always to add the entire deficit at the root of that child subtree.

Why?

Because every root-to-leaf path inside that subtree passes through that child root. A single modification there increases every path in the subtree simultaneously.

Therefore:

If the deficit is zero, no new modification is needed.
If the deficit is positive and that child root has not already been modified, we modify that child root once.
If that child root was already modified earlier while balancing its own descendants, we can simply increase it further without increasing the modification count.

This leads naturally to a DFS dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries many increment distributions
Optimal DFS DP	O(n)	O(n)	Processes each node once bottom-up

Algorithm Walkthrough

State Definition

For every node u, the DFS returns three values:

score, the equalized root-to-leaf score within the subtree rooted at u.
operations, the minimum number of modified nodes required inside that subtree.
changed, whether node u itself has already been modified.

Processing a Leaf

If u is a leaf:

Its subtree contains only one path.
No balancing is required.
Return:
score = cost[u]
operations = 0
changed = false

Processing an Internal Node

Suppose node u has children.

First recursively process every child.

For each child we obtain:

Child score.
Child operation count.
Whether the child root has already been modified.

Let:

mx = maximum child score

Balance Child Subtrees

Every child whose score is smaller than mx needs extra value:

deficit = mx - child_score

If the deficit is positive:

The optimal place to add it is the child root itself.
If that child root was not previously modified, we add one to the answer.
Mark that child root as modified.

Combine Results

The operation count for node u becomes:

sum(child_operations)
+ balancing modifications

After balancing:

score(u) = cost[u] + mx

because every child subtree now contributes exactly mx.

Return:

Equalized score.
Total modification count.
changed = false for node u, since we never modify u while processing its own subtree.

Why it works

The key invariant is that after processing a node u, all root-to-leaf paths inside u's subtree have the same score, and the reported modification count is minimal.

Whenever a child subtree is shorter than the maximum child score, adding the deficit at the child root dominates every other choice. That single node lies on every path of that subtree, so one modification can affect all required paths simultaneously. Any solution using descendants cannot use fewer modified nodes. Therefore the balancing step is optimal, and by induction the entire DFS produces the minimum number of modified nodes.

Python Solution

from typing import List
import sys

class Solution:
    def minIncrease(self, n: int, edges: List[List[int]], cost: List[int]) -> int:
        sys.setrecursionlimit(300000)

        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(u: int, parent: int):
            children = []

            for v in graph[u]:
                if v != parent:
                    children.append(v)

            if not children:
                return cost[u], 0, False

            child_info = []
            max_score = 0
            total_ops = 0

            for v in children:
                score, ops, changed = dfs(v, u)
                child_info.append([score, ops, changed])
                total_ops += ops
                max_score = max(max_score, score)

            for info in child_info:
                score, _, changed = info

                if score < max_score:
                    if not changed:
                        total_ops += 1
                    info[2] = True

            return cost[u] + max_score, total_ops, False

        _, answer, _ = dfs(0, -1)
        return answer

Implementation Explanation

The adjacency list stores the tree structure efficiently in O(n) space.

The DFS returns three values:

The equalized subtree score.
The minimum modification count.
Whether the subtree root has already been modified.

Leaves return their own cost and require no modifications.

For an internal node, we recursively solve all children and determine the maximum child score. Any child whose score is smaller must be increased. The optimal location is the child root. If that child root has not been modified before, we increase the answer by one.

After all child subtrees are balanced to the same score, the subtree rooted at the current node has equal path scores of:

cost[u] + max_child_score

The root's operation count is the final answer.

Go Solution

func minIncrease(n int, edges [][]int, cost []int) int {
	graph := make([][]int, n)

	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	type Result struct {
		score   int64
		ops     int
		changed bool
	}

	var dfs func(int, int) Result

	dfs = func(u int, parent int) Result {
		children := []int{}

		for _, v := range graph[u] {
			if v != parent {
				children = append(children, v)
			}
		}

		if len(children) == 0 {
			return Result{
				score:   int64(cost[u]),
				ops:     0,
				changed: false,
			}
		}

		childInfo := make([]Result, len(children))
		var maxScore int64
		totalOps := 0

		for i, v := range children {
			res := dfs(v, u)
			childInfo[i] = res

			totalOps += res.ops
			if res.score > maxScore {
				maxScore = res.score
			}
		}

		for i := range childInfo {
			if childInfo[i].score < maxScore {
				if !childInfo[i].changed {
					totalOps++
				}
				childInfo[i].changed = true
			}
		}

		return Result{
			score:   int64(cost[u]) + maxScore,
			ops:     totalOps,
			changed: false,
		}
	}

	return dfs(0, -1).ops
}

Go-Specific Notes

The path sums can become as large as:

10^5 × 10^9 = 10^14

which does not fit in a 32-bit integer. Therefore the implementation stores subtree scores using int64.

The logic is otherwise identical to the Python solution.

Worked Examples

Example 1

Input:

n = 3
edges = [[0,1],[0,2]]
cost = [2,1,3]

Tree:

    0(2)
   /   \
 1(1)  2(3)

Process Leaves

Node	Score	Ops	Changed
1	1	0	False
2	3	0	False

Process Root

Maximum child score:

max(1, 3) = 3

Node 1 deficit:

3 - 1 = 2

Node 1 has not been modified before.

ops += 1

Result:

Node	Score	Ops
0	2 + 3 = 5	1

Answer:

Example 2

Input:

n = 3
edges = [[0,1],[1,2]]
cost = [5,1,4]

Tree:

0
|
1
|
2

There is only one root-to-leaf path.

Node 2

Score	Ops
4	0

Node 1

Score	Ops
1 + 4 = 5	0

Node 0

Score	Ops
5 + 5 = 10	0

Answer:

Example 3

Input:

n = 5
edges = [[0,4],[0,1],[1,2],[1,3]]
cost = [3,4,1,1,7]

Tree:

Leaves

Node	Score
2	1
3	1
4	7

Node 1

Maximum child score:

No balancing needed.

Node	Score	Ops
1	4 + 1 = 5	0

Node 0

Child scores:

Child	Score
4	7
1	5

Maximum:

Deficit for child 1:

7 - 5 = 2

Modify node 1 once.

Node	Score	Ops
0	3 + 7 = 10	1

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node and edge is processed once
Space	O(n)	Adjacency list and recursion stack

The DFS visits each node exactly once. For every node, we iterate through its children a constant number of times. Since a tree contains n - 1 edges, the total work is linear in the size of the tree. The adjacency list requires O(n) memory, and the recursion stack may also reach O(n) in a degenerate chain.

Test Cases

from typing import List

s = Solution()

assert s.minIncrease(
    3,
    [[0, 1], [0, 2]],
    [2, 1, 3]
) == 1  # Example 1

assert s.minIncrease(
    3,
    [[0, 1], [1, 2]],
    [5, 1, 4]
) == 0  # Example 2, single root-to-leaf path

assert s.minIncrease(
    5,
    [[0, 4], [0, 1], [1, 2], [1, 3]],
    [3, 4, 1, 1, 7]
) == 1  # Example 3

assert s.minIncrease(
    3,
    [[0, 1], [0, 2]],
    [1, 5, 5]
) == 0  # Already equal

assert s.minIncrease(
    4,
    [[0, 1], [1, 2], [2, 3]],
    [1, 1, 1, 1]
) == 0  # Chain tree

assert s.minIncrease(
    7,
    [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],
    [1,1,1,1,1,1,1]
) == 0  # Perfect balanced tree

assert s.minIncrease(
    4,
    [[0,1],[0,2],[0,3]],
    [1,1,2,3]
) == 2  # Two children need balancing

assert s.minIncrease(
    5,
    [[0,1],[1,2],[1,3],[1,4]],
    [10,1,1,1,5]
) == 1  # Internal node modification is optimal

assert s.minIncrease(
    2,
    [[0,1]],
    [10**9, 10**9]
) == 0  # Large costs

assert s.minIncrease(
    6,
    [[0,1],[0,2],[2,3],[2,4],[4,5]],
    [5,1,2,3,4,5]
) >= 0  # General irregular tree

Test Summary

Test	Why
Example 1	Basic balancing between two leaves
Example 2	Single root-to-leaf path
Example 3	Internal node modification
Already equal tree	Verifies zero operations
Chain tree	Degenerate tree structure
Perfect balanced tree	All paths already equal
Star tree	Multiple children require balancing
Internal-node optimization	Confirms subtree-wide adjustment
Large costs	Verifies handling of big values
Irregular tree	General structural stress test

Edge Cases

Tree With Only One Root-to-Leaf Path

A chain-shaped tree contains exactly one root-to-leaf path. Since there is nothing to compare against, all root-to-leaf path scores are already equal by definition. A common bug is performing unnecessary balancing work at nodes with only one child. The DFS naturally handles this because no sibling comparisons occur.

Multiple Leaves Already Having Equal Scores

Some trees already satisfy the requirement. In these cases every child score equals the local maximum, so no deficits are detected. The algorithm never increments the modification count and correctly returns zero.

Deeply Unbalanced Trees

A tree may contain one very deep branch and one shallow branch. The path score differences can become extremely large. Since the algorithm only performs additions and comparisons of accumulated scores, and stores them in Python integers or Go int64, it handles large totals safely without depending on the magnitude of the required increments.

Internal Node Reused Across Many Paths

A subtree may contain many leaves. Increasing a node near the top of that subtree affects every leaf path beneath it. A naive solution might count modifications at several descendants. The optimal algorithm always pushes balancing adjustments to the child subtree root, ensuring one modification can cover all paths in that subtree whenever possible. This is exactly why the minimum modification count is achieved.

Problem Understanding

We are given a rooted smaller child values trigger an update.