Problem statement

An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0; its edges are given in edges, each [ui, vi]. Node i has a cost cost[i].

The score of a path is the sum of the costs of the nodes on it. You may increase the cost of any nodes by any non-negative amounts, so that afterwards every root-to-leaf path has the same score.

Return the minimum number of nodes whose cost you must increase.

Example 1

Input: n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]
Output: 1
Explanation: The paths score 3 and 5. Raising node 1's cost by 2 makes both 5.

Example 2

Input: n = 3, edges = [[0,1],[1,2]], cost = [5,1,4]
Output: 0
Explanation: There is only one root-to-leaf path.

Example 3

Input: n = 5, edges = [[0,4],[0,1],[1,2],[1,3]], cost = [3,4,1,1,7]
Output: 1
Explanation: The paths 0→4, 0→1→2 and 0→1→3 score 10, 8 and 8. Raising node 1 by 2 fixes both short paths at once.

Constraints

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i] == [ui, vi]
• 0 <= ui, vi < n
• the input is a valid tree
• cost.length == n
• 1 <= cost[i] <= 10^9

Hints for Minimum Increments to Equalize Leaf Paths

1. Hint 1

   Every root-to-leaf score can only go up, so the final common score must be the current maximum. Work out, for each node, the best score from it down to a leaf.

2. Hint 2

   At a node, all the children's subtrees must end up with the same best score — the largest child's. A child whose best is smaller needs at least one increase somewhere in its subtree.

3. Hint 3

   Increasing that child itself fixes every path through it at once. So the answer is the number of (node, child) pairs where the child's best downward score is below the maximum among its siblings.

How to solve Minimum Increments to Equalize Leaf Paths

Bottom-up, each node's subtree is made uniform first; then at the parent, every child whose uniform score falls short of the best sibling is raised once — at the child itself, which lifts its whole subtree together. That one increase per short child is unavoidable and enough.

Approach

1. Root the tree at 0 and get a BFS order.
2. In reverse BFS order compute best[u] = cost[u] + max(best[child]) (just cost[u] for a leaf).
3. At each node, let top be the maximum best among its children and count the children with best[c] < top.
4. Return the total count.

Why it works

Within the subtree of a child c that falls short, every root-to-leaf path through c is too small, and those paths share only the nodes from c up — so some node on or below c must be increased; raising c alone by top - best[c] repairs all of them. Children already at top need nothing, and increasing a node never helps a sibling subtree, so the per-node counts add up to the optimum.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Path scores reach about 10^14; keep the best values in 64-bit integers.
• Compare children against each other, not against the parent's own cost.
• Recursion over a 10^5-node path can overflow the stack; use an explicit order.

Reference solution

Python

from typing import List

def minIncrease(n: int, edges: List[List[int]], cost: List[int]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-2] * n
    parent[0] = -1
    order = [0]
    for u in order:
        for v in adj[u]:
            if parent[v] == -2:
                parent[v] = u
                order.append(v)
    best = [0] * n
    count = 0
    for u in reversed(order):
        top = 0
        for v in adj[u]:
            if v != parent[u] and best[v] > top:
                top = best[v]
        for v in adj[u]:
            if v != parent[u] and best[v] < top:
                count += 1
        best[u] = cost[u] + top
    return count

Java

public static int minIncrease(int n, int[][] edges, int[] cost) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    int[] parent = new int[n], order = new int[n];
    Arrays.fill(parent, -2);
    parent[0] = -1;
    int tail = 0;
    order[tail++] = 0;
    for (int h = 0; h < tail; h++) {
        int u = order[h];
        for (int v : adj.get(u)) if (parent[v] == -2) { parent[v] = u; order[tail++] = v; }
    }
    long[] best = new long[n];
    int count = 0;
    for (int t = n - 1; t >= 0; t--) {
        int x = order[t];
        long top = 0;
        for (int c : adj.get(x)) if (c != parent[x] && best[c] > top) top = best[c];
        for (int c : adj.get(x)) if (c != parent[x] && best[c] < top) count++;
        best[x] = cost[x] + top;
    }
    return count;
}

C++

int minIncrease(int n, vector<vector<int>>& edges, vector<int>& cost) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> parent(n, -2), order;
    parent[0] = -1;
    order.push_back(0);
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (int v : adj[u]) if (parent[v] == -2) { parent[v] = u; order.push_back(v); }
    }
    vector<long long> best(n, 0);
    int count = 0;
    for (int t = n - 1; t >= 0; t--) {
        int x = order[t];
        long long top = 0;
        for (int c : adj[x]) if (c != parent[x] && best[c] > top) top = best[c];
        for (int c : adj[x]) if (c != parent[x] && best[c] < top) count++;
        best[x] = cost[x] + top;
    }
    return count;
}

JavaScript

var minIncrease = function(n, edges, cost) {
    var adj = [], parent = [], best = [];
    for (var i = 0; i < n; i++) { adj.push([]); parent.push(-2); best.push(0); }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    parent[0] = -1;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (parent[v] === -2) { parent[v] = u; order.push(v); }
        }
    }
    var count = 0;
    for (var t = n - 1; t >= 0; t--) {
        var x = order[t], top = 0, k, c;
        for (k = 0; k < adj[x].length; k++) {
            c = adj[x][k];
            if (c !== parent[x] && best[c] > top) top = best[c];
        }
        for (k = 0; k < adj[x].length; k++) {
            c = adj[x][k];
            if (c !== parent[x] && best[c] < top) count++;
        }
        best[x] = cost[x] + top;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium