C++ || dfs with explanation and comments
\nclass Solution {\n    /*\n    First, for a number n, the number of divisors of n is O(n^(1/3)). For this problem, the maximum sum of the values in the\n    tr
```\nclass Solution {\n    /*\n    First, for a number n, the number of divisors of n is O(n^(1/3)). For this problem, the maximum sum of the values in the\n    tree is 2*10^4 * 50 = 10^6, and the maximum number of divisors here is O(100), with this number, we could consider \n    iterating through all the divisors of the sum to find the result.\n    \n    Then we come to the main part of this problem, how to check if the tree can be divided into components of same value, where the\n    number fo the components equal to a specific divisor?\n    \n    With tree problem, it is intuitive to use bfs/dfs here. I am using dfs here, since it is easier to work with recursion. The dfs algorithm\n    is shown below, notice that this is a similar dfs algorithm for calculating the size of a tree, we just change size to value here.\n    \n    The time complexity is O(n logmn), where n is the number of nodes and m is the maximum value in nums.\n        O(n) is the time complexity for one dfs traversal and O(logmn) is the maximum number of divisors.\n    \n    The auxiliary space complexity is O(n) with:\n        dfs recursion activation record: O(n)\n        neighbors lists: O(n)\n    */\n    \n    int dfs(vector<int>& nums, vector<vector<int>>& neighbors, int i, int parent, int target) {\n        // if the subtree with root i can be divided into components with same value target, then we return 0\n        int value = nums[i];\n        for (int neighbor : neighbors[i]) {\n            if (neighbor != parent) {\n                int temp = dfs(nums, neighbors, neighbor, i, target);\n                if (temp == -1) return temp; // if the subtree is invalid, then the whole tree must be also invalid\n                value += temp;\n            }\n        }\n        if (value > target) return -1;  // invalid subtree\n        if (value == target) return 0;  // find a matched component, cut off the subtree\n        return value;\n    }\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        // step 1: find the total sum of the tree\n        int sumVal = accumulate(nums.begin(), nums.end(), 0);\n        \n        // step 2: construct the neighbors lists for each of the node in the tree\n        int n = nums.size();\n        vector<vector<int>> neighbors(n);\n        for (vector<int>& edge : edges) {\n            neighbors[edge[0]].push_back(edge[1]);\n            neighbors[edge[1]].push_back(edge[0]);\n        }\n        \n        // step 3: traverse all the divisors and perform a dfs to check if we can\n        //  devide the tree into i components, where i is the divisor\n        for (int i = n; i > 1; i--) {\n            if (sumVal % i == 0) {\n                if (dfs(nums, neighbors, 0, -1, sumVal / i) == 0) return i - 1;\n            }\n        }\n        return 0;\n    }\n};\n```
['Depth-First Search', 'C']