🎯 Detailed Easy 2 DFS solution. Complete Explanation.
Intuition\n Describe your first thoughts on how to solve this problem. \nSuppose we are able to divide the tree into k components each having value x then, kx =
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSuppose we are able to divide the tree into $$k$$ components each having value $$x$$ then, $$k*x = total\\; sum\\; of\\; value\\; of\\; each\\; node$$. Since $$k$$ is an integer, $$x$$ must be a factor of $$total\\; sum$$. We calculate the $$total\\; sum$$ and try to find if each of it\'s factor can be the value of each component. If the value of each component is $$x$$ then number of components is $$ k = (total\\; sum)/ x$$. To form  $$k$$ components we need to remove $$k-1$$ edges.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n`subtree[x] stores the sum of the tree rooted at x. sub() function calculates subtree[] array first`.\nIn the `dfs()` function :\n- *adj* is the adjacency list.\n- *req* is required value of each component.\n- *k* is number of components to be formed.\n- *par* is parent node to avoid infinite recursion.\n- *nums* is the value array.\n\nIf I am at an edge `x -- y` and `subtree[y]% req == 0 and subtree[y]/req == k-1` then I can remove this edge `(k-1 is remaining number of components)`. It means after removing the edge `x -- y` , we can still form `k-1` components with the tree rooted at `y`.If only 1 component is remaining we return true. We do this over all factors of `total sum` and take the max.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\;\\;\\;\\;\\;\\;\\;O(n * sqrt(sum) )$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\;\\;\\;\\;\\;\\;\\;O(n)$$\n# Code\n```\nclass Solution {\npublic:\n    vector<int> adj[20005];\n    int subtree[20005];\n    int sub(int x, int par, vector<int> &nums){\n        int sum = nums[x];\n        for(auto y: adj[x]){\n            if(y!=par){\n                sum+=sub(y,x,nums);\n            }\n        }\n        return subtree[x] = sum;\n    }\n    bool dfs(int x , int par , int &k, int req, vector<int> & nums){\n       \n        if(k==1){\n            return true;\n        }\n        for(auto y: adj[x]){\n            if(y==par) continue;\n             if(subtree[y]%req==0&&subtree[y]/req==k-1){\n                k--;\n            }\n            if(dfs(y,x,k,req,nums)) {\n                return true;\n            }\n        }\n  \n        return false;\n    }\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        for(auto v:edges){\n            adj[v[0]].push_back(v[1]);\n            adj[v[1]].push_back(v[0]);\n        }\n        cout<<nums.size()<<endl;\n        sub(0,-1,nums);\n        int tot = 0;\n        unordered_set<int> s;\n        for(auto x:nums){\n            tot+=x;\n            s.insert(x);\n        }\n/* if each node has the same value we can delete all n-1 edges dfs*/\n        if(s.size()==1) return nums.size()-1;\n\n        int ans=1;\n        for(int i =1 ;i*i<=tot;i++){\n            if(tot%i==0){\n                int k= tot/i;\n                if(dfs(0,-1,k,i,nums)){\n                    ans = max(ans,tot/i);\n                }\n                k = i;\n                if(dfs(0,-1,k,tot/i,nums)){\n                    ans = max(ans,i);\n                }\n            }\n        }\n        return ans-1;\n        \n    }\n};\n```
['Math', 'Dynamic Programming', 'Depth-First Search', 'C++']