Problem statement

An undirected tree has n nodes numbered 0 to n - 1; node i holds the value nums[i] and edges lists its n - 1 edges.

Remove two distinct edges. The tree falls apart into exactly three connected components. Compute the XOR of all values in each component; the score of the removal is the largest of the three XORs minus the smallest.

Return the minimum score over every choice of two edges.

Example 1

Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 9
Explanation: Removing [0,1] and [1,2] leaves {1,3,4} (5 ^ 4 ^ 11 = 10), {0} (1) and {2} (5): the score is 10 - 1 = 9, and no other pair does better.

Example 2

Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
Output: 0
Explanation: Removing [1,2] and [1,3] leaves {0,1}, {2,5} and {3,4}, each with XOR 0.

Example 3

Input: nums = [7,7,7], edges = [[0,1],[1,2]]
Output: 0
Explanation: The only choice removes both edges, leaving three components of XOR 7.

Constraints

• n == nums.length
• 3 <= n <= 1000
• 1 <= nums[i] <= 10^8
• edges.length == n - 1
• edges[i].length == 2
• 0 <= a, b < n
• a != b
• edges represents a valid tree

Hints for Minimum Score After Removals on a Tree

1. Hint 1

   Root the tree. Removing an edge cuts off the subtree below it, so each removed edge is identified by its lower endpoint v, and the cut-off part has XOR sub[v] — the subtree XOR.

2. Hint 2

   For two lower endpoints u and v, the three components depend on whether one subtree contains the other. If u is an ancestor of v: sub[v], sub[u] ^ sub[v], total ^ sub[u]. If neither contains the other: sub[u], sub[v], total ^ sub[u] ^ sub[v].

3. Hint 3

   Record entry times and subtree sizes in one DFS; u is an ancestor of v exactly when tin[u] <= tin[v] < tin[u] + size[u]. Then try all O(n²) pairs.

How to solve Minimum Score After Removals on a Tree

Root the tree at node 0. Each removable edge is named by its child endpoint, and the XOR of everything below that child is precomputed. Two cuts produce three components whose XORs follow from the subtree XORs once you know whether one cut lies inside the other's subtree — which entry times answer in O(1).

Approach

1. DFS from node 0 (iteratively) to get a preorder, each node's parent, entry time tin and subtree size.
2. In reverse preorder accumulate sub[v] = nums[v] ^ XOR of sub[child]; total = sub[0].
3. For every pair of non-root nodes u < v: if u is an ancestor of v, the parts are sub[v], sub[u] ^ sub[v], total ^ sub[u]; if v is an ancestor of u, swap roles; otherwise the parts are sub[u], sub[v], total ^ sub[u] ^ sub[v].
4. Track the minimum of max(parts) - min(parts).

Why it works

XOR is its own inverse, so the XOR of a subtree with a nested subtree removed is sub[u] ^ sub[v], and the rest of the tree is total ^ (what was cut off). The three cases cover every relative position of two distinct edges in a rooted tree, so every removal pair is scored exactly.

Complexity

• Time — O(n²)
• Space — O(n)

Pitfalls

• Nested cuts and disjoint cuts give different formulas — using the disjoint formula for nested ones double-counts the inner subtree.
• The root has no parent edge, so it never names a cut.
• A recursive DFS on a 1,000-node path is fine in most languages, but Python's default recursion limit is close; an explicit stack avoids the question.

Reference solution

Python

from typing import List

def minimumScore(nums: List[int], edges: List[List[int]]) -> int:
    n = len(nums)
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    tin = [0] * n
    order = []
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        u = stack.pop()
        tin[u] = len(order)
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                stack.append(v)
    sub = nums[:]
    size = [1] * n
    for u in reversed(order):
        p = parent[u]
        if p >= 0:
            sub[p] ^= sub[u]
            size[p] += size[u]
    total = sub[0]

    def inside(u, v):  # is v in the subtree of u?
        return tin[u] <= tin[v] < tin[u] + size[u]

    best = float("inf")
    for u in range(1, n):
        for v in range(u + 1, n):
            if inside(u, v):
                a, b, c = sub[v], sub[u] ^ sub[v], total ^ sub[u]
            elif inside(v, u):
                a, b, c = sub[u], sub[v] ^ sub[u], total ^ sub[v]
            else:
                a, b, c = sub[u], sub[v], total ^ sub[u] ^ sub[v]
            best = min(best, max(a, b, c) - min(a, b, c))
    return best

Java

public static int minimumScore(int[] nums, int[][] edges) {
    int n = nums.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    int[] parent = new int[n], tin = new int[n], sub = nums.clone(), size = new int[n], order = new int[n];
    boolean[] seen = new boolean[n];
    Arrays.fill(parent, -1);
    Arrays.fill(size, 1);
    int[] stack = new int[n];
    int sp = 0, cnt = 0;
    stack[sp++] = 0;
    seen[0] = true;
    while (sp > 0) {
        int u = stack[--sp];
        tin[u] = cnt;
        order[cnt++] = u;
        for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; stack[sp++] = v; }
    }
    for (int t = n - 1; t >= 0; t--) {
        int x = order[t], p = parent[x];
        if (p >= 0) { sub[p] ^= sub[x]; size[p] += size[x]; }
    }
    int total = sub[0], best = Integer.MAX_VALUE;
    for (int a = 1; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            int p1, p2, p3;
            if (tin[a] <= tin[b] && tin[b] < tin[a] + size[a]) { p1 = sub[b]; p2 = sub[a] ^ sub[b]; p3 = total ^ sub[a]; }
            else if (tin[b] <= tin[a] && tin[a] < tin[b] + size[b]) { p1 = sub[a]; p2 = sub[b] ^ sub[a]; p3 = total ^ sub[b]; }
            else { p1 = sub[a]; p2 = sub[b]; p3 = total ^ sub[a] ^ sub[b]; }
            best = Math.min(best, Math.max(p1, Math.max(p2, p3)) - Math.min(p1, Math.min(p2, p3)));
        }
    }
    return best;
}

C++

int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    int n = nums.size();
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> parent(n, -1), tin(n), sub(nums), sz(n, 1), order;
    vector<bool> seen(n, false);
    vector<int> st = {0};
    seen[0] = true;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        tin[u] = order.size();
        order.push_back(u);
        for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; st.push_back(v); }
    }
    for (int t = n - 1; t >= 0; t--) {
        int x = order[t], p = parent[x];
        if (p >= 0) { sub[p] ^= sub[x]; sz[p] += sz[x]; }
    }
    int total = sub[0], best = INT_MAX;
    auto inside = [&](int a, int b) { return tin[a] <= tin[b] && tin[b] < tin[a] + sz[a]; };
    for (int a = 1; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            int p1, p2, p3;
            if (inside(a, b)) { p1 = sub[b]; p2 = sub[a] ^ sub[b]; p3 = total ^ sub[a]; }
            else if (inside(b, a)) { p1 = sub[a]; p2 = sub[b] ^ sub[a]; p3 = total ^ sub[b]; }
            else { p1 = sub[a]; p2 = sub[b]; p3 = total ^ sub[a] ^ sub[b]; }
            best = min(best, max({p1, p2, p3}) - min({p1, p2, p3}));
        }
    }
    return best;
}

JavaScript

var minimumScore = function(nums, edges) {
    var n = nums.length;
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) { adj[edges[e][0]].push(edges[e][1]); adj[edges[e][1]].push(edges[e][0]); }
    var parent = [], tin = [], seen = [], sub = [], size = [];
    for (var i2 = 0; i2 < n; i2++) { parent.push(-1); tin.push(0); seen.push(false); sub.push(nums[i2]); size.push(1); }
    var order = [], stack = [0];
    seen[0] = true;
    while (stack.length > 0) {
        var u = stack.pop();
        tin[u] = order.length;
        order.push(u);
        for (var k = 0; k < adj[u].length; k++) {
            var v = adj[u][k];
            if (!seen[v]) { seen[v] = true; parent[v] = u; stack.push(v); }
        }
    }
    for (var t = n - 1; t >= 0; t--) {
        var x = order[t], p = parent[x];
        if (p >= 0) { sub[p] ^= sub[x]; size[p] += size[x]; }
    }
    var total = sub[0];
    var inside = function(a, b) { return tin[a] <= tin[b] && tin[b] < tin[a] + size[a]; };
    var best = Infinity;
    for (var a = 1; a < n; a++) {
        for (var b = a + 1; b < n; b++) {
            var p1, p2, p3;
            if (inside(a, b)) { p1 = sub[b]; p2 = sub[a] ^ sub[b]; p3 = total ^ sub[a]; }
            else if (inside(b, a)) { p1 = sub[a]; p2 = sub[b] ^ sub[a]; p3 = total ^ sub[b]; }
            else { p1 = sub[a]; p2 = sub[b]; p3 = total ^ sub[a] ^ sub[b]; }
            var s = Math.max(p1, p2, p3) - Math.min(p1, p2, p3);
            if (s < best) best = s;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard