#2440

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Create Components With Same Value

Maximize the number of components in a tree with equal sums by carefully deleting edges using divisor-based logic.

array math tree depth first search enumeration

Problem Statement

You are given an undirected tree with n nodes labeled from 0 to n - 1 and an integer array nums where nums[i] represents the value of node i. A list of edges connects the nodes, forming a valid tree. You can remove edges to create multiple connected components.

The value of a component is defined as the sum of nums[i] for all nodes i in that component. Determine the maximum number of edges you can delete so that all resulting components have the same value. Return this maximum number.

Examples

Example 1

Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]]

Output: 2

The above figure shows how we can delete the edges [0,1] and [3,4]. The created components are nodes [0], [1,2,3] and [4]. The sum of the values in each component equals 6. It can be proven that no better deletion exists, so the answer is 2.

Example 2

Input: nums = [2], edges = []

Output: 0

There are no edges to be deleted.

Constraints

1 <= n <= 2 * 104
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.

Solution Approach

Compute Total Sum and Divisors

Calculate the total sum of nums. Identify all divisors of this sum because only component sums equal to a divisor can evenly partition the tree. Each divisor represents a potential target sum for components.

DFS Subtree Sum Tracking

Perform a depth-first search to compute subtree sums. At each node, check if the subtree sum matches the target divisor. If it does, mark this edge for potential deletion. This method ensures the binary-tree traversal captures all valid splits without missing nested subtrees.

Validate and Count Components

After attempting splits using DFS for each divisor, verify that all remaining subtrees can form components of equal sum. Track the number of successful splits for each divisor and return the maximum count, which represents the optimal number of edges to delete.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of divisors of the total sum multiplied by DFS traversal of n nodes, giving O(n * number_of_divisors). Space complexity is O(n) for recursion stack and tracking subtree sums.

What Interviewers Usually Probe

Expect candidates to identify the divisor-based approach early.
Look for correct DFS implementation that handles subtree sum tracking.
Check reasoning about maximum edge deletions and component count.

Common Pitfalls or Variants

Common pitfalls

Failing to consider all divisors of the total sum and missing valid partitions.
Incorrectly handling DFS so that subtree sums are miscounted.
Assuming components can have unequal sums or miscounting edge deletions.

Follow-up variants

Consider weighted nodes with larger ranges requiring careful divisor enumeration.
Use a similar approach to split a forest into equal-sum components instead of a single tree.
Modify to find minimum edges to delete to achieve exactly k equal-sum components.

FAQ

What is the key pattern in Create Components With Same Value?

The problem relies on binary-tree traversal combined with subtree sum tracking to test all divisor-based component partitions.

How do I choose target component sums?

Compute all divisors of the total sum of nums; each divisor is a candidate for the sum of all components.

Can DFS handle large trees efficiently?

Yes, a standard DFS with recursion or an explicit stack works within O(n) time for each divisor check.

Why do some edges not need deletion?

Edges connected to subtrees that already sum to the target component value should remain to preserve equal sums.

What is a common mistake when counting components?

A frequent error is double-counting or missing subtrees when validating splits for each divisor, leading to incorrect max deletions.

terminal

Solution

Solution 1: Enumeration of Connected Blocks

Assume the number of connected blocks is $k$, then the number of edges to be deleted is $k-1$, and the value of each connected block is $\frac{s}{k}$, where $s$ is the sum of the values of all nodes in $nums$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
        def dfs(i, fa):
            x = nums[i]
            for j in g[i]:
                if j != fa:
                    y = dfs(j, i)
                    if y == -1:
                        return -1
                    x += y
            if x > t:
                return -1
            return x if x < t else 0

        n = len(nums)
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        s = sum(nums)
        mx = max(nums)
        for k in range(min(n, s // mx), 1, -1):
            if s % k == 0:
                t = s // k
                if dfs(0, -1) == 0:
                    return k - 1
        return 0

Continue Practicing

#1766 tree of coprimes #2458 height of binary tree after subtree removal queries #2467 most profitable path in a tree