leetcode：6103. 从树中删除边的最小分数【dfs + 联通分量 + 子图的值记录】

分析

显然如果直接遍历两条边 + 里面再dfs会达到三次方，爆裂
因此只能遍历一条边，然后分成两个子树，得到两个异或值tot1和tot2
每个子树我们通过dfs记录这个子树的所有子树的异或值便于分割
然后我们选一颗子树和其中的一个点作为分割点，找完后，一个的分割值是sum1[uu] 另一个就是tot1^sum1[uu]

注意^的性质：0 ^ a = a; a ^ b = c => c ^ b = a

ac code

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        # 特判
        if n == 3:
            return max(nums) - min(nums)
        
        g = defaultdict(set) # remove faster
        for x, y in edges:
            g[x].add(y)
            g[y].add(x)
        
        
        # dfs 记录当前以及所有子树的异或值,用xor_sum记录(包含根的)
        # 复杂度on
        def dfs(p, u, xor_sum):
            res = nums[u] # 当前
            for v in g[u]:
                # 不准回到parent套娃
                if v == p:
                    continue
                res ^= dfs(u, v, xor_sum)
            # 更新dict
            xor_sum[u] = res
            return res
        
        res = inf
        
        # 只遍历一条边(2)，然后再根据dfs切割子树(3)即可
        for i in range(n - 1):
            u, v = edges[i]
            # cut
            g[u].remove(v)
            g[v].remove(u)
            # 得到两个分别以u和v为根子树对应的异或值和其子树的dict
            sum1 = {
    }
            tot1 = dfs(-1, u, sum1)
            sum2 = {
    }
            tot2 = dfs(-1, v, sum2)
            
            # 如果这两个子树可分，那么继续分
            if len(sum1) > 1:
                for uu in sum1:
                    if u == uu:#先当于没砍
                        continue
                    x, y, z = sum1[uu], tot1 ^ sum1[uu], tot2
                    maxn, minn = max(x, y, z), min(x, y, z)
                    if maxn - minn == 0:
                        return 0
                    res = min(res, maxn - minn)

            if len(sum2) > 1:
                for vv in sum2:
                    if v == vv:#先当于没砍
                        continue
                    x, y, z = sum2[vv], tot2 ^ sum2[vv], tot1
                    maxn, minn = max(x, y, z), min(x, y, z)
                    if maxn - minn == 0:
                        return 0
                    res = min(res, maxn - minn)
            
            # 回复原样
            g[u].add(v)
            g[v].add(u)
        
        return res

总结

对于直接无脑找两边tle的情况
可以考虑一条边，然后只有两个子树
但是我们在求其中一个子树的总异或值的时候实际上可以记录这个子树的所有子数的异或值
然后根据异或值的性质，可以快速把这个子树分成两份，这样遍历一条边on，dfs和找子树的点都是on，总的来说就是n方