leetcode：6103. Delete the minimum score of the edge from the tree [DFS + connected component + value record of the subgraph]

analysis

Obviously, if you traverse two edges directly + Inside again dfs Will reach the third power , Burst
So only one edge can be traversed , Then it is divided into two subtrees , Get two XOR values tot1 and tot2
For each subtree we pass dfs Record the XOR values of all subtrees of this subtree for easy segmentation
Then we select a subtree and one of its points as the split point , After you find it , The split value of a is sum1[uu] The other is tot1^sum1[uu]

Be careful ^ The nature of ：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)
        #  Special judgement 
        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  Record the XOR values of the current and all subtrees , use xor_sum Record ( Containing roots )
        #  Complexity on
        def dfs(p, u, xor_sum):
            res = nums[u] #  At present 
            for v in g[u]:
                #  Don't go back to parent Dolls 
                if v == p:
                    continue
                res ^= dfs(u, v, xor_sum)
            #  to update dict
            xor_sum[u] = res
            return res
        
        res = inf
        
        #  Traverse only one edge (2), And then based on dfs Cut subtree (3) that will do 
        for i in range(n - 1):
            u, v = edges[i]
            # cut
            g[u].remove(v)
            g[v].remove(u)
            #  Get two respectively with u and v Is the XOR value corresponding to the root subtree and its subtree dict
            sum1 = {
    }
            tot1 = dfs(-1, u, sum1)
            sum2 = {
    }
            tot2 = dfs(-1, v, sum2)
            
            #  If the two subtrees can be divided , Then continue to divide 
            if len(sum1) > 1:
                for uu in sum1:
                    if u == uu:# Be the first to cut 
                        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:# Be the first to cut 
                        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)
            
            #  Reply as is 
            g[u].add(v)
            g[v].add(u)
        
        return res

summary

For direct mindless looking on both sides tle The situation of
Consider an edge , Then there are only two subtrees
But when we calculate the total XOR value of one of the subtrees, we can actually record the XOR values of all the subtrees of the subtree
Then according to the nature of the XOR value , You can quickly divide this subtree into two parts , This traverses an edge on,dfs And the point of finding subtree on, In general n Fang