[C++] DFS for each divisor of the sum of all nodes in the tree
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem requires the following observations to be solved:\n\n1.) Suppose we are lo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem requires the following observations to be solved:\n\n1.) Suppose we are looking to divide the tree into components of sum s, then if a subtree has a sum of s, then it needs to be included in the final answer.\n2.) Following point 1, if there is a tree of sum m*s rooted at some node i and if we have found (m-1) components of sum s in all the subtrees of node i, then it is possible to divide the tree at node i into into m components of sum s.\n3.) We need to consider all the sums that are divisors of the total sum of the tree and choose the lowest sum for which the overall tree can be divided into equal sum components.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo check whether the given tree can be divided into equal components of sum "s", we need to check whether the number of components of sum s found in the tree is equal to "totalSum/s", where totalSum is the sum of all the nodes in the overall tree.\n\nThe 2nd observation points to a recursive approach, so we are going to use DFS to count the number of components for each divisor of totalSum.\n\n# Complexity\n- Time complexity: O(N*k) where k is the number of factors of totalSum\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N) - for storing the tree\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    struct CompositeSum {\n        int componentsFound;\n        int sum;\n    };\n\n    CompositeSum dfs(int s, int parent, int targetSum, vector<vector<int>>& tree, \n                    vector<int>& nums) {\n        int currSum = nums[s], currComponents = 0;\n        for (int nbr: tree[s]) {\n            if (nbr == parent) {\n                continue;\n            }\n            CompositeSum subResult = dfs(nbr, s, targetSum, tree, nums);\n            currSum += subResult.sum;\n            currComponents += subResult.componentsFound;\n        }\n\n        if (currSum % targetSum == 0 && (currComponents == currSum/targetSum-1)) {\n            currComponents++;\n        }\n\n        CompositeSum fin = {currComponents, currSum};\n        return fin;\n    }\n\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        //create the tree\n        int N = nums.size();\n        vector<vector<int>> tree(N);\n        for (vector<int>& edge: edges) {\n            tree[edge[0]].push_back(edge[1]);\n            tree[edge[1]].push_back(edge[0]);\n        }\n\n        //calculate the sum and its factors;\n        int sum = 0;\n        for (int num: nums) {\n            sum += num;\n        }\n        vector<int> factors;\n        for (int i = 1; i*i <= sum; i++) {\n            if (sum%i == 0) {\n                factors.push_back(i);\n                factors.push_back(sum/i);\n            }\n        }\n        sort(factors.begin(), factors.end(), greater<int>());\n\n        int ans = 0;\n        for (int factor: factors) {\n            CompositeSum curr = dfs(0, -1, factor, tree, nums);\n            if (curr.componentsFound == sum/factor) {\n                ans = sum/factor-1;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']