There is an undirected tree with n nodes labeled from 0 to n - 1.
You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are allowed to delete some edges, splitting the tree into multiple connected components. Let the value of a component be the sum of all nums[i] for which node i is in the component.
Return the maximum number of edges you can delete, such that every connected component in the tree has the same value.
Example 1:
Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 2 Explanation: 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 Explanation: There are no edges to be deleted.
Constraints:
1 <= n <= 2 * 104nums.length == n1 <= nums[i] <= 50edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges represents a valid tree.Problem Overview: You are given a tree where each node has a value. Remove edges so that every connected component has the same total value. The goal is to maximize the number of removed edges while keeping all resulting components with identical sums.
Approach 1: Depth First Search with Target Sum Enumeration (O(n * d) time, O(n) space)
The key observation: if the total sum of all node values is S, every component must sum to a divisor of S. Enumerate possible target sums and verify whether the tree can be split so each component equals that value. For each candidate target, run a Depth‑First Search on the tree to compute subtree sums. When a subtree sum reaches the target, treat it as a completed component and return 0 upward so the parent doesn't double count it. If any subtree exceeds the target, that configuration is invalid. The number of successful target partitions determines how many edges you can remove.
This works because every valid partition must align with subtree boundaries in a tree. DFS naturally aggregates values bottom‑up and lets you detect when a component sum matches the target.
Approach 2: Union-Find Component Aggregation (O(n α(n)) time, O(n) space)
An alternative model treats nodes as components and progressively merges them while tracking component sums using a Union-Find structure. Nodes are joined along edges while ensuring the combined sum does not exceed the chosen target value. When a merged component exactly equals the target sum, it becomes a finalized component and stops merging further. The disjoint-set structure allows efficient union and find operations while maintaining component sums.
This approach is less common for interviews but demonstrates how component constraints can be enforced dynamically with disjoint sets. It works well when you want explicit component tracking rather than recursive subtree accumulation.
Recommended for interviews: The DFS enumeration approach. It directly leverages tree properties and shows strong understanding of subtree aggregation. Start by computing the total sum, enumerate valid target sums, and validate each using DFS. The Union-Find approach is more specialized and rarely expected in interviews.
In this approach, we utilize Depth First Search (DFS) to traverse the tree and calculate the total sum of all node values. Then, we attempt to partition the tree into connected components that have equal value. This involves checking each divisor of the total sum and seeing if it can be used as the target value for each component.
This C implementation begins by computing the total sum of the node values. Using an adjacency list (represented with arrays here due to C's static nature), it prepares the tree structure, allowing for DFS traversal.
For each divisor of the total sum, it attempts to split the tree into components whose sum of nodes equals the divisor. The maximum number of deletions observed (which equals the number of unused edges) represents our solution.
Time Complexity: O(n * sqrt(sum(nums))) where sum(nums) is the sum of all node values as we potentially check multiple divisors and perform a DFS for each.
Space Complexity: O(n), primarily for the adjacency list and visited status arrays.
This approach leverages the Union-Find (also known as Disjoint Set Union, DSU) data structure to effectively manage connected components in the tree dynamically. By maintaining a Union-Find structure, components can be merged or split efficiently. We will essentially attempt to simulate the partitions dynamically based on the total sum and divisors.
This solution in Python uses a Union-Find data structure to efficiently manage tree components. By continuously merging nodes and recalculating sums, the program ensures that each component's sum is validated against a divisor. Optimal deletions are calculated for setups where each resulting component sum equals the divisor's multiples or entire divisor.
Python
Time Complexity: O(n * sqrt(sum(nums)) * α(n)) due to the amortized inverse Ackermann function associated with union-find operations.
Space Complexity: O(n) for maintaining union-find structures and component sums.
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.
We enumerate k from large to small. If there exists a k such that \frac{s}{k} is an integer, and the value of each connected block obtained is equal, then directly return k-1. The initial value of k is min(n, \frac{s}{mx}), where mx is the maximum value in nums.
The key point is to judge whether for a given \frac{s}{k}, it is possible to divide several subtrees such that the value of each subtree is \frac{s}{k}.
Here we use the dfs function to judge. We recursively traverse from top to bottom to calculate the value of each subtree. If the sum of the subtree values is exactly \frac{s}{k}, it means that the division is successful at this time. We set the value to 0 and return it to the upper level, indicating that this subtree can be disconnected from the parent node. If the sum of the subtree values is greater than \frac{s}{k}, it means that the division fails at this time. We return -1, indicating that it cannot be divided.
The time complexity is O(n times \sqrt{s}), where n and s are the length of nums and the sum of the values of all nodes in nums, respectively.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(n * sqrt(sum(nums))) where sum(nums) is the sum of all node values as we potentially check multiple divisors and perform a DFS for each. Space Complexity: O(n), primarily for the adjacency list and visited status arrays. |
| Union-Find Approach | Time Complexity: O(n * sqrt(sum(nums)) * α(n)) due to the amortized inverse Ackermann function associated with union-find operations. Space Complexity: O(n) for maintaining union-find structures and component sums. |
| Enumeration of Connected Blocks | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Target Sum Enumeration | O(n * d) | O(n) | General case for trees. Best interview approach for validating equal-sum components. |
| Union-Find Component Aggregation | O(n α(n)) | O(n) | Useful when explicitly tracking merged components or experimenting with disjoint-set structures. |
Biweekly Contest 89 | 6211. Create Components With Same Value • codingMohan • 1,334 views views
Watch 4 more video solutions →Practice Create Components With Same Value with our built-in code editor and test cases.
Practice on FleetCode