#2322

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Minimum Score After Removals on a Tree

Compute the minimum score after removing two edges in a tree using DFS and XOR-based component tracking efficiently.

array bit manipulation tree depth first search

Problem Statement

You are given a tree with n nodes labeled from 0 to n - 1, represented by an array nums where nums[i] is the value of node i, and a list of edges connecting the nodes. The tree is undirected and connected, ensuring exactly n - 1 edges.

The task is to remove any two distinct edges to create three separate connected components. Compute the XOR of the values in each component, and the score is the difference between the largest and smallest XOR. Return the minimum score achievable from all possible edge removal pairs.

Examples

Example 1

Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]

Output: 9

The diagram above shows a way to make a pair of removals.

The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1.
The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5. The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9. It can be shown that no other pair of removals will obtain a smaller score than 9.

Example 2

Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]

Output: 0

The diagram above shows a way to make a pair of removals.

The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0. The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0. We cannot obtain a smaller score than 0.

Constraints

n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.

Solution Approach

DFS for Subtree XOR Precomputation

Perform a depth-first search from any node to compute the XOR of values in each subtree. Store these results to avoid recalculating XORs when simulating edge removals.

Iterate Edge Pairs and Compute Scores

For each first edge removed, consider removing each other edge and split the tree into three components. Use precomputed subtree XORs to quickly compute the XOR of each component and calculate the score.

Track Minimal XOR Difference

Maintain a variable for the minimal score across all edge pairs. After evaluating all combinations, the minimal score is the answer. Focus on handling overlapping subtrees correctly to avoid double-counting nodes.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

Time complexity is O(n^2) due to evaluating each pair of edges for removal and computing the XOR differences using precomputed subtree values. Space complexity is O(n) to store the XOR of each subtree and track visited nodes during DFS.

What Interviewers Usually Probe

Look for a solution using binary-tree traversal and subtree state tracking.
Expect handling of XOR aggregation efficiently to avoid recalculation for each edge pair.
Check that the candidate properly identifies overlapping subtrees when removing edges.

Common Pitfalls or Variants

Common pitfalls

Failing to precompute subtree XORs and recalculating for every edge pair.
Double-counting nodes when the two removed edges affect nested subtrees.
Ignoring edge cases where one component might contain only a single node.

Follow-up variants

Instead of XOR, compute sum differences among components after edge removals.
Apply the problem to a weighted tree where edge weights influence component value.
Generalize to removing k edges to create k+1 components with minimal XOR score.

FAQ

What is the best approach for Minimum Score After Removals on a Tree?

Use DFS to precompute subtree XORs and iterate over edge pairs, calculating component XORs to find the minimum score.

Why is XOR used instead of sum in this problem?

XOR preserves unique value combinations and ensures the score captures distinct component differences, aligning with the problem's requirements.

Can the tree have single-node components after removal?

Yes, removing edges may isolate a single node. Its XOR value is just the node's own value, and it must be included in score calculations.

What is the typical complexity of this solution?

Time complexity is O(n^2) for evaluating all edge pairs, with space O(n) for storing subtree XORs and DFS bookkeeping.

How do I handle overlapping subtrees in edge removal?

Track each subtree's XOR carefully and account for nodes only once when edges share ancestor-descendant relationships.

terminal

Solution

Solution 1: DFS + Subtree XOR Sum

We denote the XOR sum of the tree as $s$, i.e., $s = \text{nums}[0] \oplus \text{nums}[1] \oplus \ldots \oplus \text{nums}[n-1]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        def dfs(i: int, fa: int) -> int:
            res = nums[i]
            for j in g[i]:
                if j != fa:
                    res ^= dfs(j, i)
            return res

        def dfs2(i: int, fa: int) -> int:
            nonlocal s, s1, ans
            res = nums[i]
            for j in g[i]:
                if j != fa:
                    s2 = dfs2(j, i)
                    res ^= s2
                    mx = max(s ^ s1, s2, s1 ^ s2)
                    mn = min(s ^ s1, s2, s1 ^ s2)
                    ans = min(ans, mx - mn)
            return res

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        s = reduce(lambda x, y: x ^ y, nums)
        n = len(nums)
        ans = inf
        for i in range(n):
            for j in g[i]:
                s1 = dfs(i, j)
                dfs2(i, j)
        return ans

Continue Practicing

#2920 maximum points after collecting coins from all nodes #2368 reachable nodes with restrictions #2246 longest path with different adjacent characters