Python | Factorization + DFS
Let s = sum(nums).  Let t is the sum of a component, which is unknown right now.  But, because each component has the same sum, s % t == 0 must hold.\n\nSo firs
Let `s = sum(nums)`.  Let `t` is the sum of a component, which is unknown right now.  But, because each component has the same sum, `s % t == 0` must hold.\n\nSo first, we find all the possible `t`s.  We can try from `1` to `ceil(sqrt(s))`, and we sort the `t`s from small to large.  Remember `t` can be larger than `sqrt(s)`.  For `s = i * j`, both `i` and `j` are candidates of `t`.\n\nAnd then, we try using each `t` as the component sum and see if that is feasible.  We use a DFS on the tree.  For each sub-tree, there are 3 situations:\n1. `sum < t`, then we should not cut off this sub-tree.\n2. `sum == t`, then we should cut off this sub-tree, and `+1` to the cut counter.\n3. `sum > t`, then this `t` is infeasible.  Terminate and try next `t`.\n\nIf `t` is feasible, then we can return the cut counter.  No need to try the larger `t`s.\n\nThe amount of `t`s is in `O(sqrt(N))`, and DFS costs `O(N)`.  Overall is `O(N*sqrt(N))`.\n\n```\nclass Solution:\n    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n        n = len(nums)\n        if n <= 1: return 0\n        s = sum(nums)\n        m = max(nums)\n        \n        f = set()\n        for i in range(1, ceil(sqrt(s))):\n            if s % i == 0:\n                if i >= m:\n                    f.add(i)\n                j = s // i\n                if j >= m:\n                    f.add(j)\n        f = sorted(f)\n        \n        g = [[] for _ in range(n)]\n        for a, b in edges:\n            g[a].append(b)\n            g[b].append(a)\n            \n        c = 0\n        t = 0\n        def rec(p, pp):\n            nonlocal c\n            r = nums[p]\n            for q in g[p]:\n                if q == pp: continue\n                r += rec(q, p)\n            if r == t:\n                c += 1\n                return 0\n            elif r > t:\n                raise Exception("")\n            else:\n                return r\n        for t in f:\n            try:\n                c = 0\n                rec(0, -1)\n                return c-1\n            except:\n                pass\n```
['Depth-First Search', 'Recursion', 'Python']