[Python] Get factors of sum all nodes then check
Intuition\n- Sum of each connected component must be values in factors of sum(nums), and at least max(nums).\n- So get factors of sum all nodes then check if we
# Intuition\n- Sum of each connected component must be values in factors of `sum(nums)`, and at least `max(nums)`.\n- So get factors of sum all nodes then check if we can split into connected component, where sum of each connected component is equal to factor.\n\n# Complexity\n- Time complexity: `O(sqrt(SUM_ALL_NODE) + N*log(SUM_ALL_NODE))`, where `SUM_ALL_NODE <= 10^6` is number of all nodes, `N <= 2*10^4` is number of nodes.\n    - `factors` is up to `log(SUM_ALL_NODE)` elements.\n    - `dfs()` function cost `O(N)`\n\n- Space complexity: `O(log(SUM_ALL_NODE) + N)`\n\n# Code\n```python\nclass Solution:\n    def getFactors(self, x):\n        factors = []\n        for i in range(1, int(sqrt(x)) + 1):\n            if x % i != 0: continue\n            factors.append(i)\n            if x // i != i: factors.append(x // i)\n        return factors\n\n    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n        n = len(nums)\n        graph = defaultdict(list)\n        for a, b in edges:\n            graph[a].append(b)\n            graph[b].append(a)\n\n        self.cntRemainZero = 0\n        def dfs(u, p, sumPerComponent): # return remain of the subtree with root `u`\n            remain = nums[u]\n            for v in graph[u]:\n                if v == p: continue\n                remain += dfs(v, u, sumPerComponent)\n                \n            remain %= sumPerComponent\n            if remain == 0:\n                self.cntRemainZero += 1\n                \n            return remain\n        \n        def isGood(sumPerComponent, expectedNumOfComponents):\n            self.cntRemainZero = 0\n            dfs(0, -1, sumPerComponent)\n            return self.cntRemainZero == expectedNumOfComponents\n        \n        sumAllNodes, maxNum = sum(nums), max(nums)\n        for sumPerComponent in sorted(self.getFactors(sumAllNodes)):\n            if sumPerComponent < maxNum: continue  # at least maxNum\n            expectedNumOfComponents = sumAllNodes // sumPerComponent\n            if isGood(sumPerComponent, expectedNumOfComponents):\n                return expectedNumOfComponents - 1 # Need to cut `numOfComponent - 1` edges to make `numOfComponent` connected component\n            \n        return 0\n```
['Python3']