Short DFS in Python3, Faster Than 77%
Approach\n Describe your approach to solving the problem. \nMerging the solutions from bottom to up with DFS. The only cut is that the size of candidate compone
# Approach\n<!-- Describe your approach to solving the problem. -->\nMerging the solutions from bottom to up with DFS. The only cut is that the size of candidate components should divide the sum of all nodes. The cut is very important for the time complexity. \n\n# Code\n```\nclass Solution:\n    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n        overall_total = sum(nums)\n        graph = defaultdict(set)\n        for a, b in edges:\n            graph[a].add(b)\n            graph[b].add(a)\n\n        def dfs(v=0, parent=-1):\n            nonlocal overall_total\n            res = {}\n            total = nums[v]\n            for u in graph[v]:\n                if u != parent:\n                    r = dfs(u, v)\n                    k = next(iter(r.keys()))\n                    total += r[k][0] * k + r[k][1]\n                    for k in r:\n                        if overall_total % k != 0:\n                            continue\n                        if k not in res:\n                            res[k] = [r[k][0], r[k][1], 1]\n                        else:\n                            res[k][0] += r[k][0]\n                            res[k][1] += r[k][1]\n                            res[k][2] += 1\n                \n            solutions = {total: (1, 0)}\n            for k in res:\n                if overall_total % k != 0:\n                    continue\n                remains = total - (k * res[k][0])\n                if remains == k:\n                    solutions[k] = (res[k][0] + 1, 0)\n                elif remains < k:\n                    solutions[k] = (res[k][0], remains)\n            return solutions\n\n        ans = dfs()\n        k = min(k for k, v in ans.items() if v[1] == 0)\n        return ans[k][0] - 1\n```
['Math', 'Depth-First Search', 'Python3']