Problem statement

An undirected tree has n nodes numbered 0 to n - 1; node i has the value nums[i], and edges lists the tree's n - 1 edges.

You may delete some of the edges, splitting the tree into connected components. The value of a component is the sum of nums over its nodes.

Return the maximum number of edges you can delete so that every component ends up with the same value.

Example 1

Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 2
Explanation: Delete [0,1] and [3,4]: the components {0}, {1,2,3} and {4} all have value 6.

Example 2

Input: nums = [2], edges = []
Output: 0
Explanation: A single node has no edges to delete.

Example 3

Input: nums = [1,1,1,1], edges = [[0,1],[1,2],[2,3]]
Output: 3
Explanation: Deleting every edge leaves four components of value 1.

Constraints

• 1 <= n <= 2 * 10^4
• nums.length == n
• 1 <= nums[i] <= 50
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• edges represents a valid tree

Hints for Create Components With Same Value

1. Hint 1

   If the tree ends in k components of equal value, each one is worth exactly total / k — so k must divide the total sum.

2. Hint 2

   For a fixed target value t, cut greedily from the leaves up: a subtree whose remaining sum reaches exactly t must be cut off, and one whose sum exceeds t makes t impossible.

3. Hint 3

   Try k from the largest possible value downwards (it is at most n); the first k whose greedy check succeeds gives k - 1 deletions.

How to solve Create Components With Same Value

Deleting k - 1 edges makes k components, all worth total / k. For a candidate k, a post-order pass decides feasibility: each subtree passes up the sum of what has not been cut off yet; that sum must never exceed the target, and it is cut (reset to 0) the moment it equals the target.

Approach

1. Compute total = sum(nums) and a DFS order of the tree from node 0.
2. For k = n down to 1, skipping k that do not divide total: let t = total / k.
3. Walk the nodes in reverse DFS order, setting rem[v] = nums[v] + rem of its children. If rem[v] > t the target fails; if rem[v] == t, set rem[v] = 0 (the edge above v is cut).
4. If no node failed and the root ends at rem = 0, return k - 1.

Why it works

With all values positive, a subtree whose leftover sum equals t cannot keep anything above it in the same component without exceeding t, so cutting there is forced; a leftover above t cannot be fixed by cuts higher up. Hence the greedy check succeeds exactly when a split into components worth t exists, and the largest feasible k maximises the deletions.

Complexity

• Time — O(n · d(total))
• Space — O(n)

Pitfalls

• k cannot exceed n, and t cannot be below max(nums) — both prune the loop.
• The root must finish at exactly 0 left over; anything else means the last component is short.
• Recursion on a 20,000-node path overflows some stacks — a precomputed DFS order processed in reverse avoids it.

Reference solution

Python

from typing import List

def componentValue(nums: List[int], edges: List[List[int]]) -> int:
    n = len(nums)
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    order = []
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                stack.append(v)
    total = sum(nums)
    biggest = max(nums)
    for k in range(min(n, total // biggest), 0, -1):
        if total % k:
            continue
        t = total // k
        rem = nums[:]
        ok = True
        for u in reversed(order):
            if rem[u] > t:
                ok = False
                break
            if rem[u] == t:
                rem[u] = 0
            if parent[u] >= 0:
                rem[parent[u]] += rem[u]
        if ok and rem[0] == 0:
            return k - 1
    return 0

Java

public static int componentValue(int[] nums, int[][] edges) {
    int n = nums.length;
    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], stack = new int[n];
    boolean[] seen = new boolean[n];
    Arrays.fill(parent, -1);
    int sp = 0, cnt = 0;
    stack[sp++] = 0;
    seen[0] = true;
    while (sp > 0) {
        int u = stack[--sp];
        order[cnt++] = u;
        for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; stack[sp++] = v; }
    }
    int total = 0, biggest = 0;
    for (int x : nums) { total += x; biggest = Math.max(biggest, x); }
    for (int k = Math.min(n, total / biggest); k >= 1; k--) {
        if (total % k != 0) continue;
        int t = total / k;
        int[] rem = nums.clone();
        boolean ok = true;
        for (int p = n - 1; p >= 0; p--) {
            int x = order[p];
            if (rem[x] > t) { ok = false; break; }
            if (rem[x] == t) rem[x] = 0;
            if (parent[x] >= 0) rem[parent[x]] += rem[x];
        }
        if (ok && rem[0] == 0) return k - 1;
    }
    return 0;
}

C++

int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
    int n = nums.size();
    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, -1), order, st = {0};
    vector<bool> seen(n, false);
    seen[0] = true;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);
        for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; st.push_back(v); }
    }
    int total = 0, biggest = 0;
    for (int x : nums) { total += x; biggest = max(biggest, x); }
    for (int k = min(n, total / biggest); k >= 1; k--) {
        if (total % k != 0) continue;
        int t = total / k;
        vector<int> rem(nums);
        bool ok = true;
        for (int p = n - 1; p >= 0; p--) {
            int x = order[p];
            if (rem[x] > t) { ok = false; break; }
            if (rem[x] == t) rem[x] = 0;
            if (parent[x] >= 0) rem[parent[x]] += rem[x];
        }
        if (ok && rem[0] == 0) return k - 1;
    }
    return 0;
}

JavaScript

var componentValue = function(nums, edges) {
    var n = nums.length;
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) { adj[edges[e][0]].push(edges[e][1]); adj[edges[e][1]].push(edges[e][0]); }
    var parent = [], seen = [];
    for (var i2 = 0; i2 < n; i2++) { parent.push(-1); seen.push(false); }
    var order = [], stack = [0];
    seen[0] = true;
    while (stack.length > 0) {
        var u = stack.pop();
        order.push(u);
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (!seen[v]) { seen[v] = true; parent[v] = u; stack.push(v); }
        }
    }
    var total = 0, biggest = 0;
    for (var i3 = 0; i3 < n; i3++) { total += nums[i3]; if (nums[i3] > biggest) biggest = nums[i3]; }
    for (var k = Math.min(n, Math.floor(total / biggest)); k >= 1; k--) {
        if (total % k !== 0) continue;
        var t = total / k, rem = nums.slice(), ok = true;
        for (var p = n - 1; p >= 0; p--) {
            var x = order[p];
            if (rem[x] > t) { ok = false; break; }
            if (rem[x] === t) rem[x] = 0;
            if (parent[x] >= 0) rem[parent[x]] += rem[x];
        }
        if (ok && rem[0] === 0) return k - 1;
    }
    return 0;
};

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

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard