[Python] Explanation with pictures, BFS
Instead of\n- Splitting trees aimlessly until we cut it into equal parts.\n\nWe do:\n- Set a value target, check if there is a way to split the tree into parts 
Instead of\n- Splitting trees aimlessly until we cut it into equal parts.\n\nWe do:\n- Set a value `target`, check if there is a way to split the tree into parts with value `target`.\n\nStart with brute force, can we split trees into all segments of `target = 1`, or `target = 2`, or `target = 3`... ? Well we don\'t need to try every possible target value. If we can split tree into `k` parts, it means the sum of values `sum(N)` must be divisible by `k`. We only need to test the number of times equal to the number of `sum(N)`\'s factors. (Given `sum(N) = 15`, we only need to try `target = 1, 3, 5, 15`)\n\n\nNow for a `target`, how to check if the tree can be splited into `k` parts of value `target`?\n\n![image](https://assets.leetcode.com/users/images/f55605c5-52e5-4b69-8e88-9787bb4570f0_1665852053.7543595.png)\n\nWe can use a toplogical-sort-like strategy, start with leaf nodes (nodes with degree of 1). If a leaf value is less than `target`, then it must be connected to its parent in order to make `target`. Thus we push leaf value to its \'parent\' (or \'root\'? \'neighbor\'? correct my terminology if I am wrong), and decrement the degree of parent node by 1. \n\n![image](https://assets.leetcode.com/users/images/017b88e4-a1d8-43c1-9f80-17c6428b66c6_1665852056.9383192.png)\n\nNote some edge cases:\n\n- If a leaf value equals `target`, then we don\'t push its value, just reduce its the degree of its \'parent\' by 1.\n- If a leaf value is larger than `target`, then there is no way to split tree into parts of value `target`. \n- If we run into the last node, just check if its value equals `target`.\n\nAs shown below:\n- Don\'t increment the middle node\'s value by `6`.\n- The node value is larger than `6`, we will keep pushing its value (end up with fail anyway)\n- The last node\'s value is not `6`, the split fails.\n\n![image](https://assets.leetcode.com/users/images/7344df0f-4909-4a0f-8529-666fe27af093_1665853429.1268094.png)\n\n\n**python**\n```\nclass Solution:\n    def componentValue(self, N:List[int], E: List[List[int]]) -> int:\n        ma, ss, n = max(N), sum(N), len(N)\n        G = collections.defaultdict(set)\n        degree = [0] * n\n        for a, b in E:\n            degree[a] += 1\n            degree[b] += 1\n            G[a].add(b)\n            G[b].add(a)\n            \n        def bfs(target):\n            V, deg = N[:], degree[:]\n            dq = collections.deque([i for i, d in enumerate(degree) if d == 1])\n            \n            while dq:\n                ci = dq.popleft()\n                deg[ci] = 0\n                for nxt in G[ci]:\n                    if V[ci] != target: V[nxt] += V[ci] # Edge case 1.\n                    deg[nxt] -= 1\n                    if deg[nxt] == 0:\n                        return V[nxt] == target # Edge case 3.\n                    elif deg[nxt] == 1:\n                        dq.append(nxt)     \n           \n        for cand in range(min(N), ss):\n            if ss % cand == 0 and bfs(cand):\n                return ss // cand - 1\n        return 0\n```
[]