LC 6211. 创建价值相同的连通块

https://leetcode.cn/contest/biweekly-contest-89/problems/create-components-with-same-value/

这题迟迟不敢下手，也是不知道里面有什么玄机。看了第一名的题解，大致确定思路就是枚举所有可能的价值，然后验证这个价值是否可以满足。

我之前没有太写过这种在树上的DFS算法，看了第一名题解，觉得相比图的遍历可以简化不少：不用维护visited, 只需要记录parent就行，访问的时候避开parent.

然后这个验证过程也很有技巧：

先验证子树是否满足，假设子树返回值是r
- 如果 r<target 的话，那么就需要累加到当前节点上来，否则子树是无法独立满足条件的
- 如果 r>target 的话，那么直接返回 false.
- 如果 r == target 的话，那么子树可以独立出去认为返回值是0.
将无法独立出去的子树 r 累加，和当前节点相加，进行判断。

看了他写的代码之后觉得非常简单，但是遍历和子树拆解纠缠在一起，就迟迟不敢下手。

class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        adj = [[] for _ in range(n)]
        for x, y in edges:
            adj[x].append(y)
            adj[y].append(x)

        def dfs(x, parent, target):
            s = nums[x]

            for y in adj[x]:
                if y == parent: continue
                res = dfs(y, x, target)
                if res < 0:
                    return -1
                s += res

            if s > target:
                return -1
            if s == target:
                return 0
            return s

        M = max(nums)
        total = sum(nums)
        part = total // M
        for p in reversed(range(1, part + 1)):
            if total % p == 0:
                target = total // p
                assert target >= M
                if dfs(0, -1, target) == 0:
                    return p - 1