C++ || DFS || Math
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to partition the tree into connected components, each having the same sum o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to partition the tree into connected components, each having the same sum of node values. The total sum of the array should be divisible by the number of components we want to form, which leads us to check the divisors of the sum. For each divisor, we attempt to recursively split the tree.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tGraph Representation: We represent the tree using an adjacency list based on the edges.\n2.\tDFS Function (f): We perform a depth-first search (DFS) on the tree starting from node 0. As we traverse, we accumulate the node values. If at any point the accumulated value exceeds the target sum for a component, we return an invalid state (a large value).\n\t\u2022\tIf the accumulated value exactly equals the target sum, we reset it to 0 since we successfully formed one component.\n3.\tDivisor Checking: We loop over the possible number of components (starting from n to 2) and check if the total sum can be divided evenly into that many components. For each divisor, we try to partition the tree.\n4.\tReturn Result: The maximum number of components that can be formed is the result.\n# Complexity\n- Time complexity: $$O(n * sqrt(sum(nums)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    vector<vector<int>> adj;\n    vector<int> vis;\n    int target;\nprivate:\n    int f(int node, vector<int>& nums){\n        vis[node] = nums[node];\n        for(auto adjNode: adj[node]){\n            if(vis[adjNode]) continue;\n            vis[node] += f(adjNode, nums);\n            if(vis[node] > target) return 1e7;\n        }\n        if(vis[node] == target) return 0;\n        return vis[node];\n    }\n\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        int n = nums.size();\n        int sum = accumulate(nums.begin(), nums.end(), 0);\n        adj.resize(n);\n        for(auto& it: edges){\n            adj[it[0]].push_back(it[1]);\n            adj[it[1]].push_back(it[0]);\n        }\n\n        for (int i=n; i>1; i--) {\n            if(sum % i) continue;\n            target = sum/i;\n            vis = vector<int>(n);\n            if(f(0, nums) == 0) return i-1;\n        }\n        \n        return 0;\n    }\n};\n```
['Array', 'Math', 'Depth-First Search', 'C++']