Easy DFS + Math || C++
Intuition\nLet\'s say each component has value x. It may be possible to make such component only when sum of all nodes is divisible by x. Given the constraints,
# Intuition\nLet\'s say each component has value x. It may be possible to make such component only when sum of all nodes is divisible by x. Given the constraints, total sum of all nodes <= 1e6. Number of divisors of a number n are approximately \u221Bn, which means n\u221B1e6 should pass here. So just iterate over all divisors and try to divide tree into components with value equal to that divisor.\n\n# Approach\nWe will iterate over all divisors of total sum of all nodes (sum), and then do dfs to try dividing tree into components with value equal to that divisor. Whenever we get value of a subtree equal to divisor, we disconnect it with it\'s parent (remove one edge).\n\n# Complexity\n- Time complexity: O(n\u221B(sum))\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int dfs(int node, int parent, vector<int>& nums, vector<vector<int>>& graph, int& remedges, int i){\n        int cur=0;\n        for(auto& g:graph[node]){\n            if(g==parent) continue;\n            cur+=dfs(g,node,nums,graph,remedges,i);\n        }\n        cur+=nums[node];\n        if(cur==i){\n            cur=0;\n            remedges++;\n        }\n        return cur;\n    }\n    \n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        int n=nums.size();\n        vector<vector<int>> graph(n);\n        for(auto& e:edges){\n            graph[e[0]].push_back(e[1]);\n            graph[e[1]].push_back(e[0]);\n        }\n        int ans=0,total=accumulate(nums.begin(),nums.end(),0),\n        mini=*min_element(nums.begin(),nums.end());\n        for(int i=mini;i<=total/2;++i){\n            if(total%i==0){\n                int remedges=0;\n                if(dfs(0,-1,nums,graph,remedges,i)==0){\n                    ans=max(ans,remedges-1);\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Tree', 'Depth-First Search', 'Enumeration', 'C++']