[Python] One Pass DFS to count, optimized with module, O(n) * ((factor of sum(nums)) - max(nums))
First, get all subtree sum dfs start from any node(here is 0).As every compent we get is divisor of sum(nums), we iterate all k in range(max(nums), s). sum(c fo
First, get all subtree sum dfs start from any node(here is 0).As every compent we get is divisor of sum(nums), we iterate all k in range(max(nums), s). *sum(c for v, c in dt.items() if v % k == 0)* is used to get all subtree sum is k * t(1 <= t <= s // k).\n```\nclass Solution:\n    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n        graph = [[] for _ in range(len(nums))]\n        for u, v in edges:\n            graph[u].append(v)\n            graph[v].append(u)\n        dt, visited = dict(), set()\n        def dfs(v):\n            visited.add(v)\n            ret = nums[v]\n            for u in graph[v]:\n                if u not in visited: ret += dfs(u)\n            dt[ret] = dt.get(ret, 0) + 1\n            return ret\n        s = sum(nums)\n        dfs(0)\n        for k in range(max(nums), s):\n            if s % k: continue\n            if sum(c for v, c in dt.items() if v % k == 0) == s // k: return s // k - 1\n        return 0\n```
[]