Minimum Score After Removals on a Tree

hard trees dfs xor euler tour

Problem

Given a tree with n nodes where nums[i] is the value of node i, remove two distinct edges to split the tree into three connected components. For each component take the XOR of its node values; the score of a removal is the largest component XOR minus the smallest. Return the minimum score over every pair of removals.

Inputnums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]

Output9

Components {1,3,4}, {0}, {2} give XORs 5^4^11=10, 1, 5. Score = 10 − 1 = 9, the minimum possible.

nums (comma-separated)

edges (a:b, comma-separated)

def minimum_score(nums, edges):
    n = len(nums)
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b); g[b].append(a)
    xr = nums[:]          # subtree XOR
    tin = [0] * n; tout = [0] * n
    timer = [0]
    def dfs(u, p):
        tin[u] = timer[0]; timer[0] += 1
        for v in g[u]:
            if v != p:
                dfs(v, u)
                xr[u] ^= xr[v]
        tout[u] = timer[0]; timer[0] += 1
    dfs(0, -1)
    total = xr[0]
    anc = lambda u, v: tin[u] <= tin[v] and tout[v] <= tout[u]
    best = float("inf")
    for i in range(1, n):
        for j in range(i + 1, n):
            if anc(i, j):
                a, b, c = xr[j], xr[i] ^ xr[j], total ^ xr[i]
            elif anc(j, i):
                a, b, c = xr[i], xr[j] ^ xr[i], total ^ xr[j]
            else:
                a, b, c = xr[i], xr[j], total ^ xr[i] ^ xr[j]
            best = min(best, max(a, b, c) - min(a, b, c))
    return best

function minimumScore(nums, edges) {
  const n = nums.length;
  const g = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { g[a].push(b); g[b].push(a); }
  const xr = nums.slice();
  const tin = Array(n), tout = Array(n);
  let timer = 0;
  const dfs = (u, p) => {
    tin[u] = timer++;
    for (const v of g[u]) if (v !== p) { dfs(v, u); xr[u] ^= xr[v]; }
    tout[u] = timer++;
  };
  dfs(0, -1);
  const total = xr[0];
  const anc = (u, v) => tin[u] <= tin[v] && tout[v] <= tout[u];
  let best = Infinity;
  for (let i = 1; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      let a, b, c;
      if (anc(i, j)) { a = xr[j]; b = xr[i] ^ xr[j]; c = total ^ xr[i]; }
      else if (anc(j, i)) { a = xr[i]; b = xr[j] ^ xr[i]; c = total ^ xr[j]; }
      else { a = xr[i]; b = xr[j]; c = total ^ xr[i] ^ xr[j]; }
      best = Math.min(best, Math.max(a, b, c) - Math.min(a, b, c));
    }
  }
  return best;
}

int minimumScore(int[] nums, int[][] edges) {
    int n = nums.length;
    List<Integer>[] g = new List[n];
    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
    for (int[] e : edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); }
    int[] xr = nums.clone(), tin = new int[n], tout = new int[n];
    int[] timer = {0};
    dfs(0, -1, g, xr, tin, tout, timer);
    int total = xr[0], best = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int a, b, c;
            if (anc(i, j, tin, tout)) { a = xr[j]; b = xr[i] ^ xr[j]; c = total ^ xr[i]; }
            else if (anc(j, i, tin, tout)) { a = xr[i]; b = xr[j] ^ xr[i]; c = total ^ xr[j]; }
            else { a = xr[i]; b = xr[j]; c = total ^ xr[i] ^ xr[j]; }
            int hi = Math.max(a, Math.max(b, c)), lo = Math.min(a, Math.min(b, c));
            best = Math.min(best, hi - lo);
        }
    return best;
}

int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    int n = nums.size();
    vector<vector<int>> g(n);
    for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
    vector<int> xr = nums, tin(n), tout(n);
    int timer = 0;
    function<void(int,int)> dfs = [&](int u, int p) {
        tin[u] = timer++;
        for (int v : g[u]) if (v != p) { dfs(v, u); xr[u] ^= xr[v]; }
        tout[u] = timer++;
    };
    dfs(0, -1);
    int total = xr[0], best = INT_MAX;
    auto anc = [&](int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; };
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int a, b, c;
            if (anc(i, j)) { a = xr[j]; b = xr[i] ^ xr[j]; c = total ^ xr[i]; }
            else if (anc(j, i)) { a = xr[i]; b = xr[j] ^ xr[i]; c = total ^ xr[j]; }
            else { a = xr[i]; b = xr[j]; c = total ^ xr[i] ^ xr[j]; }
            best = min(best, max({a, b, c}) - min({a, b, c}));
        }
    return best;
}

Explanation

Removing an edge in a rooted tree cuts off exactly one subtree. So if we root the tree at node 0, every removable edge corresponds to a non-root node u — cutting that edge detaches u's entire subtree. This lets us describe every pair of removals by two nodes instead of two edges.

A single DFS computes xr[u], the XOR of all values in u's subtree, by XOR-folding the children into the node. The same DFS records Euler-tour entry/exit times tin/tout. With those, u is an ancestor of v iff tin[u] ≤ tin[v] and tout[v] ≤ tout[u] — an O(1) test, no extra walking.

For a pair of cut nodes i and j there are two shapes. If one is an ancestor of the other (say i is ancestor of j), the components are the inner subtree xr[j], the ring between them xr[i] ^ xr[j], and the rest total ^ xr[i].

Otherwise the two subtrees are disjoint, giving xr[i], xr[j], and everything else total ^ xr[i] ^ xr[j]. XOR is self-inverse, so subtracting a subtree from the whole is just another XOR.

For each of the three XOR values we take max − min as the score and keep the minimum across all O(n²) pairs. Total work is O(n²) after the linear DFS.

Time: O(n²) Space: O(n)