Minimum score after removals on a tree

Array Bit Manipulation Tree Depth-First Search

76.2% acceptance

Feb 25, 2026

814

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given a 0-indexed integer array nums and a 2D integer array edges. Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, compute the XOR of each component; the score is max_xor - min_xor. Return the minimum score of any possible pair of edge removals.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    for e in &edges {
      let (a, b) = (e[0] as usize, e[1] as usize);
      adj[a].push(b);
      adj[b].push(a);
    }

    let mut subtree_xor = nums.clone();
    let mut in_time = vec![0usize; n];
    let mut out_time = vec![0usize; n];
    let mut parent = vec![n; n];
    let mut timer = 0usize;

    // Iterative DFS with in/out timestamps and subtree XOR computation
    let mut stack: Vec<(usize, usize, bool)> = vec![(0, n, false)];
    while let Some((v, p, processed)) = stack.pop() {
      if processed {
        out_time[v] = timer;
        timer += 1;
        for &u in &adj[v] {
          if u != p {
            subtree_xor[v] ^= subtree_xor[u];
          }
        }
      } else {
        parent[v] = p;
        in_time[v] = timer;
        timer += 1;
        stack.push((v, p, true));
        for &u in &adj[v] {
          if u != p {
            stack.push((u, v, false));
          }
        }
      }
    }

    let total = subtree_xor[0];

    let is_anc = |u: usize, v: usize| -> bool {
      in_time[u] <= in_time[v] && out_time[v] <= out_time[u]
    };

    let mut ans = i32::MAX;
    // Each non-root node i represents cutting the edge (parent[i], i)
    for i in 1..n {
      for j in (i + 1)..n {
        let xi = subtree_xor[i];
        let xj = subtree_xor[j];
        let (a, b, c) = if is_anc(i, j) {
          (xj, xi ^ xj, total ^ xi)
        } else if is_anc(j, i) {
          (xi, xj ^ xi, total ^ xj)
        } else {
          (xi, xj, total ^ xi ^ xj)
        };
        let mx = a.max(b).max(c);
        let mn = a.min(b).min(c);
        if mx - mn < ans {
          ans = mx - mn;
        }
      }
    }
    ans
  }
}