DFS Solution
IntuitionThe problem requires dividing the tree into components of equal value by removing edges. Initially, the solution can be thought of as exploring potenti
# Intuition
The problem requires dividing the tree into components of equal value by removing edges. Initially, the solution can be thought of as exploring potential "component values" (sum of values in each component) and checking if the tree can be split accordingly. This approach stems from the observation that the total sum of all node values must be divisible by the desired component value.

# Approach
1. **Graph Representation**: Represent the tree as an adjacency list for easy traversal.
2. **Sum and Divisors**: Calculate the total sum of node values. Iterate through all possible divisors of this total sum as potential "component values."
3. **DFS Validation**: Use Depth-First Search (DFS) to determine if the tree can be split into components where the sum of each component equals the target value.
   - If a subtree forms a valid component, return `0` for that branch, indicating that the component is complete.
   - If a subtree's sum exceeds the target, the current configuration is invalid.
4. **Result Calculation**: For each valid "component value," calculate the number of edges removed (`total_sum // target - 1`), which represents the maximum number of components.

# Complexity
- Time complexity:
  - Constructing the adjacency list takes $$O(n)$$.
  - Testing all divisors of `total_sum` involves a loop over potential divisors (approximately $$O(\sqrt {{total\_sum}})$$) with a DFS call for each divisor. Each DFS traversal is $$O(n)$$.
  - Overall complexity: $$O(n \times \sqrt {\text{total\_sum}})$$.

- Space complexity:
  - The adjacency list uses $$O(n)$$ space.
  - The recursion stack for DFS can go up to $$O(n)$$.
  - Overall complexity: $$O(n)$$.
# Code
```python3 []
class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
        if len(nums) == 1:
            return 0
        
        adj_list = defaultdict(list)
        for i, j in edges:
            adj_list[i].append(j)
            adj_list[j].append(i)
        
        total_sum = sum(nums)
        
        # Helper function to perform DFS and check if the tree can be split with `target` as the component value
        def dfs(curr, parent, target):
            total = nums[curr]
            for child in adj_list[curr]:
                if child != parent:
                    subtree_sum = dfs(child, curr, target)
                    # If the subtree can't form a valid component, return a large number to indicate failure
                    if subtree_sum == -1:
                        return -1
                    total += subtree_sum
            
            # If this subtree forms a valid component, "cut" it and return 0
            if total == target:
                return 0
            
            # Otherwise, return the current total for further propagation
            return total if total < target else -1
        
        # Try all possible component values (divisors of total_sum)
        for target in range(1, total_sum + 1):
            if total_sum % target == 0:
                # Try to partition the tree with this target value
                if dfs(0, -1, target) == 0:
                    # If successful, calculate the number of edges removed
                    return total_sum // target - 1
        
        return 0
```
['Python3']