# Create Components With Same Value
**Difficulty:** HARD
[External](https://leetcode.com/problems/create-components-with-same-value)
Canonical: https://scaleengineer.com/dsa/problems/create-components-with-same-value
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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:**

![](https://assets.glich.co/dsa/create-components-with-same-value/image0.png) 

**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 * 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.

# Approaches
## Brute Force by Deleting Edge Subsets
This approach exhaustively checks every possible way to partition the tree. Since a tree with `n` nodes has `n-1` edges, there are `2^(n-1)` possible subsets of edges to delete. For each subset, the algorithm forms the resulting components, calculates their values, and checks if they are all equal. It keeps track of the maximum number of deleted edges that results in a valid partition.
**Time:** O(2^(n-1) * n). There are `2^(n-1)` subsets of edges. For each, building the graph and finding components takes O(n + (n-1)) = O(n) time. · **Space:** O(n) to store the adjacency list and visited array for each configuration.
**Pros:** Simple to understand and implement.; Guaranteed to be correct as it checks all possibilities.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints (`n` up to 20,000).
### Explanation
The core idea is to treat the problem as finding the best subset of edges to delete. We can represent each subset using a bitmask of length `n-1`. If the `i`-th bit is set, we delete the `i`-th edge; otherwise, we keep it.

For each of the `2^(n-1)` masks, we perform the following steps:
1.  **Build a graph**: We create an adjacency list representing the graph formed by the edges we decided to keep.
2.  **Find Components and Sums**: We traverse the graph to identify all connected components. A `visited` array helps track nodes that have already been assigned to a component. For each component found, we calculate the sum of its node values.
3.  **Validate Partition**: We store the sums of all components in a list. If this list is not empty, we check if all its elements are equal to the first element. 
4.  **Update Maximum**: If all component sums are equal, it means we've found a valid partition. We then compare the number of edges we deleted for this partition with the maximum found so far and update it if necessary.

This method is guaranteed to find the correct answer because it explores the entire search space, but its exponential time complexity makes it impractical for anything but very small trees.

```java
// Conceptual implementation of the brute-force approach.
// This will be too slow for the given constraints (Time Limit Exceeded).
class Solution {
    public int componentValue(int[] nums, int[][] edges) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }
        int numEdges = edges.length;
        int maxDeleted = 0;

        for (int i = 0; i < (1 << numEdges); i++) {
            List<Integer>[] adj = new ArrayList[n];
            for (int j = 0; j < n; j++) {
                adj[j] = new ArrayList<>();
            }
            int deletedCount = 0;

            for (int j = 0; j < numEdges; j++) {
                if (((i >> j) & 1) == 1) { // Edge j is deleted
                    deletedCount++;
                } else { // Edge j is kept
                    adj[edges[j][0]].add(edges[j][1]);
                    adj[edges[j][1]].add(edges[j][0]);
                }
            }

            List<Long> componentSums = new ArrayList<>();
            boolean[] visited = new boolean[n];
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    long currentSum = 0;
                    Queue<Integer> q = new LinkedList<>();
                    q.add(j);
                    visited[j] = true;
                    while (!q.isEmpty()) {
                        int u = q.poll();
                        currentSum += nums[u];
                        for (int v : adj[u]) {
                            if (!visited[v]) {
                                visited[v] = true;
                                q.add(v);
                            }
                        }
                    }
                    componentSums.add(currentSum);
                }
            }

            boolean allEqual = true;
            if (componentSums.size() > 1) {
                long firstSum = componentSums.get(0);
                for (int j = 1; j < componentSums.size(); j++) {
                    if (componentSums.get(j) != firstSum) {
                        allEqual = false;
                        break;
                    }
                }
            }

            if (allEqual) {
                maxDeleted = Math.max(maxDeleted, deletedCount);
            }
        }
        return maxDeleted;
    }
}
```
### Algorithm
- Initialize `max_deleted_edges` to 0.
- Iterate through all `2^(n-1)` subsets of edges. Each subset represents a potential set of edges to delete.
- For each subset:
  - Count the number of edges to be deleted, `current_deleted_count`.
  - Construct a graph using only the edges that are *not* in the current subset.
  - Find all connected components in this new graph using a traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS).
  - For each component, calculate the sum of its node values.
  - Check if all component sums are identical.
  - If they are, update `max_deleted_edges = max(max_deleted_edges, current_deleted_count)`.
- After checking all subsets, return `max_deleted_edges`.

## Checking Divisors of Total Sum with DFS
This efficient approach is based on a crucial observation: if the tree is split into `c` components of equal value, then the value of each component must be a divisor of the total sum of all node values. Instead of trying all edge deletions, we can iterate through all possible valid component values. We want to maximize the number of deleted edges, which is equivalent to maximizing the number of components `c`. Therefore, we can iterate `c` from `n` down to 1, find the corresponding target value (`totalSum / c`), and check if a partition with that target value is possible. This check can be performed efficiently with a single Depth First Search (DFS).
**Time:** O(d(totalSum) * n), where `d(totalSum)` is the number of divisors of the total sum. For the given constraints, `totalSum` is at most `2*10^4 * 50 = 10^6`. The number of divisors for numbers up to `10^6` is small (at most 240). Thus, the complexity is effectively near-linear in `n`. · **Space:** O(n) for building the adjacency list and for the recursion stack depth in the worst-case (a skewed tree).
**Pros:** Highly efficient and passes within the time limits.; Reduces the search space from exponential to a small number of divisor checks.
**Cons:** Relies on a number theory insight (divisibility), which might not be immediately obvious.; The recursive DFS implementation requires careful handling of return values to signal success, failure, or a partial sum.
### Explanation
The algorithm proceeds as follows:

1.  **Calculate Total Sum**: First, compute the sum of all node values, `totalSum`.
2.  **Iterate Potential Partitions**: We want to maximize the number of components, `c`. The maximum possible value for `c` is `n`, and the minimum is 1. We iterate `c` from `n` down to 2. For each `c`, we check if it can be a valid number of components.
3.  **Check Divisibility**: For a partition into `c` components to be possible, `totalSum` must be perfectly divisible by `c`. If `totalSum % c != 0`, we skip to the next value of `c`.
4.  **Verify Partition with DFS**: If `totalSum` is divisible by `c`, we set `target = totalSum / c`. We then need to verify if the tree can indeed be partitioned into components of this `target` value. This is the core of the algorithm, which we solve using a post-order DFS traversal.

The `dfs(u, parent)` function calculates the sum of the subtree rooted at `u` and returns one of three things:
-   The sum of its subtree component if it's less than `target`.
-   `0` if its subtree sum is exactly `target`. This signifies that the subtree forms a valid component, and we 'cut' the edge to its parent by not propagating its sum upwards.
-   A special value (e.g., greater than `target`) to signal that a partition with this `target` is impossible because a subtree sum has already exceeded it.

We start the DFS from the root (e.g., node 0). If the final result of `dfs(0, -1)` is `0`, it means the entire tree was successfully partitioned into components of value `target`. Since we iterate `c` from largest to smallest, the first `c` that passes this check gives the maximum number of components. The answer is `c - 1`.

```java
class Solution {
    private List<Integer>[] adj;
    private int[] nums;
    private long targetSum;
    private long totalSum; // Use long to be safe, though int is sufficient here

    public int componentValue(int[] nums, int[][] edges) {
        int n = nums.length;
        this.nums = nums;
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (n <= 1) {
            return 0;
        }

        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        // Iterate on k = number of components, from n down to 2
        for (int k = n; k >= 2; k--) {
            if (totalSum % k == 0) {
                this.targetSum = totalSum / k;
                if (dfs(0, -1) == 0) {
                    return k - 1;
                }
            }
        }

        return 0;
    }

    private long dfs(int u, int p) {
        long currentSum = nums[u];
        for (int v : adj[u]) {
            if (v == p) continue;
            long childSum = dfs(v, u);
            
            // If a child subtree sum already exceeds target, or if the check failed deeper down,
            // propagate the failure. A value > targetSum indicates failure.
            if (childSum > targetSum) {
                return childSum;
            }
            currentSum += childSum;
        }

        if (currentSum == targetSum) {
            // This subtree forms a component, cut the edge to parent by returning 0.
            return 0; 
        }
        
        // If currentSum > targetSum, this partition is not possible.
        // Return a value that signals failure.
        if (currentSum > targetSum) {
            return totalSum + 1; // Any value > targetSum would work.
        }

        // Pass the sum up to the parent.
        return currentSum; 
    }
}
```
### Algorithm
- Calculate `totalSum`, the sum of all elements in `nums`.
- Build an adjacency list for the tree from the `edges` array.
- Iterate through the possible number of components, `c`, from `n` down to `2`.
- For each `c`, check if `totalSum` is divisible by `c`.
  - If it is, let `target = totalSum / c`. This is the required value for each component.
  - Call a DFS-based function, `check(target)`, to verify if the tree can be partitioned into components of this value.
- The `check` function uses a post-order traversal (`dfs(u, parent)`):
  - For a node `u`, it recursively calculates the sum of its subtree, assuming child subtrees that form a valid component have been 'cut'.
  - `dfs(u, parent)` returns the sum of the component containing `u`.
  - If `dfs` for a subtree returns a sum equal to `target`, it means a component is formed. This call then returns `0` to its parent, simulating an edge cut.
  - If a subtree sum exceeds `target`, the partition is impossible for this `target`. The function propagates a failure signal.
  - The initial call `dfs(0, -1)` must return `0` for a successful partition of the entire tree.
- If `check(target)` is successful, we have found the maximum possible `c`. Return `c - 1` as the answer.
- If the loop completes without finding a valid partition, it means no edges can be deleted. Return `0`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int[] nums;
private
  int t;
public
  int componentValue(int[] nums, int[][] edges) {
    int n = nums.length;
    g = new List[n];
    this.nums = nums;
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    int s = sum(nums), mx = max(nums);
    for (int k = Math.min(n, s / mx); k > 1; --k) {
      if (s % k == 0) {
        t = s / k;
        if (dfs(0, -1) == 0) {
          return k - 1;
        }
      }
    }
    return 0;
  }
private
  int dfs(int i, int fa) {
    int x = nums[i];
    for (int j : g[i]) {
      if (j != fa) {
        int y = dfs(j, i);
        if (y == -1) {
          return -1;
        }
        x += y;
      }
    }
    if (x > t) {
      return -1;
    }
    return x < t ? x : 0;
  }
private
  int sum(int[] arr) {
    int x = 0;
    for (int v : arr) {
      x += v;
    }
    return x;
  }
private
  int max(int[] arr) {
    int x = arr[0];
    for (int v : arr) {
      x = Math.max(x, v);
    }
    return x;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int componentValue(vector<int> &nums, vector<vector<int>> &edges) {
    int n = nums.size();
    int s = accumulate(nums.begin(), nums.end(), 0);
    int mx = *max_element(nums.begin(), nums.end());
    int t = 0;
    unordered_map<int, vector<int>> g;
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    function<int(int, int)> dfs = [&](int i, int fa) -> int {
      int x = nums[i];
      for (int j : g[i]) {
        if (j != fa) {
          int y = dfs(j, i);
          if (y == -1)
            return -1;
          x += y;
        }
      }
      if (x > t)
        return -1;
      return x < t ? x : 0;
    };
    for (int k = min(n, s / mx); k > 1; --k) {
      if (s % k == 0) {
        t = s / k;
        if (dfs(0, -1) == 0) {
          return k - 1;
        }
      }
    }
    return 0;
  }
};

```

### Python

```python
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

```