Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Root the tree at zero. Cutting any edge isolates the subtree rooted at its child endpoint, the endpoint farther from the root, so two cuts are represented by two non-root nodes. Their subtrees are either disjoint or one contains the other; XOR cancellation gives all three component values in either case.

Approach

Compute each subtree's XOR and explicitly store its descendant-node set. Enumerate every pair of distinct non-root nodes. If j lies inside i, the component XORs are total XOR subtree[i], subtree[i] XOR subtree[j], and subtree[j]; use the symmetric formula for the reverse containment. For disjoint subtrees, use their two XORs and total XOR subtree[i] XOR subtree[j]. Minimize the difference between the largest and smallest of these three values. Explicit descendant sets, rather than traversal timestamps, determine containment in the reference code.

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        adj = defaultdict(list)

        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        xor = [0] * n
        def xor_dfs(node, par):
            curr = nums[node]

            for nei in adj[node]:
                if nei != par:
                    curr ^= xor_dfs(nei, node)
            
            xor[node] = curr
            return curr
        xor_dfs(0, -1)

        subtree_nodes = [0] * n
        def subtree_nodes_dfs(node, par):
            curr = set([node])

            for nei in adj[node]:
                if nei != par:
                    curr |= subtree_nodes_dfs(nei, node)
            
            subtree_nodes[node] = curr
            return curr
        subtree_nodes_dfs(0, -1)

        res = float('inf')

        for i in range(1, n):
            for j in range(i + 1, n):
                if j in subtree_nodes[i]:
                    a = xor[0] ^ xor[i]
                    b = xor[i] ^ xor[j]
                    c = xor[j]
                elif i in subtree_nodes[j]:
                    a = xor[0] ^ xor[j]
                    b = xor[j] ^ xor[i]
                    c = xor[i]
                else:
                    a = xor[0] ^ xor[i] ^ xor[j]
                    b = xor[i]
                    c = xor[j]
                res = min(res, max(a, b, c) - min(a, b, c))
        
        return res

Complexity analysis

Let n = nums.length and H be the tree height. Both displayed implementations compute subtree XOR values and explicit subtree-node sets, then examine all pairs of removed edges. Time is O(n^2), auxiliary subtree-set space is O(n^2), and recursion uses O(H) stack space. Python can exceed its default recursion limit on an allowed 1000-node path.