# 2440. Create Components With Same Value       • Time: $O(|\sqrt{\Sigma\texttt{nums[i]}}| \cdot n)$
• Space: $O(n)$
  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class Solution { public: int componentValue(vector& nums, vector>& edges) { const int n = nums.size(); const int sum = accumulate(begin(nums), end(nums), 0); vector> graph(n); for (const vector& edge : edges) { const int u = edge; const int v = edge; graph[u].push_back(v); graph[v].push_back(u); } for (int i = n; i > 1; --i) // split the tree into i parts, i.e., delete (i - 1) edges if (sum % i == 0 && dfs(nums, graph, 0, sum / i, vector(n)) == 0) return i - 1; return 0; } private: static constexpr int kMax = 1'000'000'000; // Returns the sum of the subtree rooted at u minus the sum of the deleted // subtrees. int dfs(const vector& nums, const vector>& graph, int u, int target, vector&& seen) { int sum = nums[u]; seen[u] = true; for (const int v : graph[u]) { if (seen[v]) continue; sum += dfs(nums, graph, v, target, move(seen)); if (sum > target) return kMax; } // Delete the tree that has sum == target if (sum == target) return 0; return sum; } }; 
  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public int componentValue(int[] nums, int[][] edges) { final int n = nums.length; final int sum = Arrays.stream(nums).sum(); List[] graph = new List[n]; for (int i = 0; i < graph.length; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge; final int v = edge; graph[u].add(v); graph[v].add(u); } for (int i = n; i > 1; --i) // split the tree into i parts, i.e., delete (i - 1) edges if (sum % i == 0 && dfs(nums, graph, 0, sum / i, new boolean[n]) == 0) return i - 1; return 0; } private static final int kMax = 1_000_000_000; // Returns the sum of the subtree rooted at u minus the sum of the deleted subtrees. private int dfs(int[] nums, List[] graph, int u, int target, boolean[] seen) { int sum = nums[u]; seen[u] = true; for (final int v : graph[u]) { if (seen[v]) continue; sum += dfs(nums, graph, v, target, seen); if (sum > target) return kMax; } // Delete the tree that has sum == target if (sum == target) return 0; return sum; } } 
  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 28 29 30 31 32 33 34 class Solution: def componentValue(self, nums: List[int], edges: List[List[int]]) -> int: kMax = 1_000_000_000 n = len(nums) summ = sum(nums) graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) # Returns the sum of the subtree rooted at u minus the sum of the deleted subtrees. def dfs(u: int, target: int, seen: Set[bool]) -> int: summ = nums[u] seen.add(u) for v in graph[u]: if v in seen: continue summ += dfs(v, target, seen) if summ > target: return kMax # Delete the tree that has sum == target if summ == target: return 0 return summ for i in range(n, 1, -1): # split the tree into i parts, i.e., delete (i - 1) edges if summ % i == 0 and dfs(0, summ // i, set()) == 0: return i - 1 return 0