LeetCode Solutions Blog

Minimum Score After Removals on a Tree

Number: 2400

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an undirected tree with n nodes (labeled 0 to n-1) and an array of values for each node, remove exactly two distinct edges. Removing two edges splits the tree into three connected components. For each component, compute the XOR of all values in that component. The score for a pair of edge removals is defined as the difference between the maximum and minimum of these three XOR values. The goal is to return the minimum such score possible over all choices of two edges to remove.

Key Insights

Root the tree arbitrarily (e.g., at node 0) and perform a DFS to compute:
- The XOR of all node values in every subtree.
- Entry and exit times (tin/tout) to later determine ancestry relationships.
Every edge in the tree (between a parent and child) is a candidate removal edge.
For any two candidate edges, check if one is inside the subtree defined by the other (i.e. they are nested) or if they are disjoint.
When processing a pair of removals:
- If the two removed edges are disjoint then the three components are the subtrees from each removal and the remainder of the tree.
- If one removal is nested inside the other, the calculations differ slightly because one component is “cut out” of the other.
Use the total XOR (of all nodes) and the precomputed subtree XOR values to quickly calculate the XOR values for each resulting component.
An overall O(n^2) solution is acceptable given n is up to 1000.

Space and Time Complexity

Time Complexity: O(n^2) – Two nested loops iterating over candidate edges (up to O(n) candidates each). Space Complexity: O(n) – Storing DFS traversal information, subtree XORs, and candidate edge list.

Solution

We solve the problem by first rooting the tree and using DFS to compute two key pieces of information: the XOR sum of the subtree for every node and the entry/exit timestamps (tin/tout) which let us decide if one node is an ancestor of another. Every edge from parent to child becomes a candidate for removal.

For a pair of removed edges, let one edge be (p1, v1) and the other be (p2, v2) (with p1 and p2 being the parents given the DFS tree structure). If one removed subtree is inside the other, then the three component XORs are:

comp1: XOR of the inner subtree,
comp2: XOR of the “remainder” of the outer subtree after removing the inner subtree, and
comp3: XOR of the rest of the tree (total XOR without the outer subtree). Otherwise (if disjoint) the three components are:
comp1: XOR of the subtree at v1,
comp2: XOR of the subtree at v2, and
comp3: total XOR XOR comp1 XOR comp2.

Maintain a global minimum difference across all candidate pairs and return it at the end.

Code Solutions

# Python solution with detailed line-by-line comments

def minimumScore(nums, edges):
    from collections import defaultdict
    n = len(nums)
    
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Initialization arrays:
    # subtree_xor[i] stores XOR of subtree rooted at i
    subtree_xor = [0] * n
    # tin and tout for DFS timing to help decide ancestry
    tin = [0] * n
    tout = [0] * n
    time = [0]  # using list so that it can be modified inside dfs
    
    # candidate_edges will store tuples: (parent, child) corresponding to edge removal
    candidate_edges = []
    
    # DFS traversal to compute subtree XOR and tin/tout times
    def dfs(node, parent):
        tin[node] = time[0]
        time[0] += 1
        xor_val = nums[node]
        # For each neighbor that is not the parent perform DFS
        for neighbor in tree[node]:
            if neighbor == parent:
                continue
            candidate_edges.append((node, neighbor))  # store removal candidate edge
            xor_val ^= dfs(neighbor, node)
        subtree_xor[node] = xor_val
        tout[node] = time[0]
        time[0] += 1
        return xor_val

    total_xor = dfs(0, -1)
    min_score = float("inf")
    
    # A helper function to check if node u is an ancestor of node v
    def is_ancestor(u, v):
        return tin[u] < tin[v] and tout[v] < tout[u]
    
    # Process all pairs of candidate removal edges
    L = len(candidate_edges)
    for i in range(L):
        p1, c1 = candidate_edges[i]
        for j in range(i+1, L):
            p2, c2 = candidate_edges[j]
            # Three components' XOR values initialized
            if is_ancestor(c1, c2):
                # Edge j is in the subtree of edge i. 
                comp1 = subtree_xor[c2]                # Component from second removal (inner)
                comp2 = subtree_xor[c1] ^ subtree_xor[c2]  # The remainder in the subtree of c1 excluding c2's subtree
                comp3 = total_xor ^ subtree_xor[c1]       # Remainder of the tree
            elif is_ancestor(c2, c1):
                # Edge i is in the subtree of edge j.
                comp1 = subtree_xor[c1]                # Component from first removal (inner)
                comp2 = subtree_xor[c2] ^ subtree_xor[c1]  # The remainder in the subtree of c2 excluding c1's subtree
                comp3 = total_xor ^ subtree_xor[c2]       # Remainder of the tree
            else:
                # The two removed edges are in disjoint parts of the tree.
                comp1 = subtree_xor[c1]                # Component from first removal
                comp2 = subtree_xor[c2]                # Component from second removal
                comp3 = total_xor ^ subtree_xor[c1] ^ subtree_xor[c2]  # The rest of the tree
            current_max = max(comp1, comp2, comp3)
            current_min = min(comp1, comp2, comp3)
            min_score = min(min_score, current_max - current_min)
    return min_score

# Example usage
print(minimumScore([1,5,5,4,11], [[0,1],[1,2],[1,3],[3,4]]))