Minimum Score After Removals on a Tree
HardUpdated: Jul 24, 2025
Practice on:
Problem
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 of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:
- Get the XOR of all the values of the nodes for each of the three components respectively.
- The difference between the largest XOR value and the smallest XOR value is the score of the pair.
- For example, say the three components have the node values:
[4,5,7],[1,9], and[3,3,3]. The three XOR values are4 ^ 5 ^ 7 = _**6**_,1 ^ 9 = _**8**_, and3 ^ 3 ^ 3 = _**3**_. The largest XOR value is8and the smallest XOR value is3. The score is then8 - 3 = 5.
Return theminimum score of any possible pair of edge removals on the given tree.
Examples
Example 1
graph TD 1((5)) 0((1)) 2((5)) 3((4)) 4((11)) 0 --- 1 1 --- 2 1 --- 3 3 --- 4
Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 9
Explanation: 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
graph TD 0((5)) 1((5)) 2((2)) 3((4)) 4((4)) 5((2)) 0 --- 1 1 --- 2 1 --- 3 3 --- 4 2 --- 5
Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
Output: 0
Explanation: 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.length3 <= n <= 10001 <= nums[i] <= 10^8edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.
Solution
Method 1 – DFS Subtree XORs + Edge Removal Simulation
Intuition
For each edge, removing it splits the tree into two subtrees. Removing a second edge in one subtree splits it further. Precompute subtree XORs for all nodes. For each pair of edges, simulate removals and compute the three component XORs.
Approach
- Build tree, run DFS to compute subtree XORs and parent for each node.
- For each edge (u,v), let v be child of u. For each other edge (x,y), let y be child of x.
- For each pair, determine the three components and their XORs using subtree XORs and total XOR.
- Track the minimum score.
Code
C++
#include <vector>
#include <algorithm>
class Solution {
public:
int minimumScore(std::vector<int>& nums, std::vector<std::vector<int>>& edges) {
int n = nums.size();
std::vector<std::vector<int>> g(n);
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
std::vector<int> xorv(n), parent(n,-1);
std::function<void(int,int)> dfs = [&](int u,int p){
xorv[u]=nums[u]; parent[u]=p;
for (int v : g[u]) if (v!=p) { dfs(v,u); xorv[u]^=xorv[v]; }
};
dfs(0,-1);
int res = INT_MAX, total = xorv[0];
for (auto& e1 : edges) {
int a = e1[0], b = e1[1];
if (parent[b]!=a) std::swap(a,b);
for (auto& e2 : edges) {
if (e1==e2) continue;
int c = e2[0], d = e2[1];
if (parent[d]!=c) std::swap(c,d);
int x, y, z;
if (isAncestor(b,d,parent)) {
x = xorv[d]; y = xorv[b]^xorv[d]; z = total^xorv[b];
} else if (isAncestor(d,b,parent)) {
x = xorv[b]; y = xorv[d]^xorv[b]; z = total^xorv[d];
} else {
x = xorv[b]; y = xorv[d]; z = total^xorv[b]^xorv[d];
}
int mx = std::max({x,y,z}), mn = std::min({x,y,z});
res = std::min(res, mx-mn);
}
}
return res;
}
bool isAncestor(int u, int v, std::vector<int>& parent) {
while (v!=-1) { if (v==u) return true; v=parent[v]; }
return false;
}
};
Go
func minimumScore(nums []int, edges [][]int) int {
n := len(nums)
g := make([][]int, n)
for _, e := range edges {
g[e[0]] = append(g[e[0]], e[1])
g[e[1]] = append(g[e[1]], e[0])
}
xorv := make([]int, n)
parent := make([]int, n)
for i := range parent { parent[i] = -1 }
var dfs func(int,int)
dfs = func(u,p int) {
xorv[u]=nums[u]; parent[u]=p
for _,v := range g[u] { if v!=p { dfs(v,u); xorv[u]^=xorv[v] } }
}
dfs(0,-1)
total := xorv[0]
res := 1<<30
isAncestor := func(u,v int) bool {
for v!=-1 { if v==u { return true }; v=parent[v] }
return false
}
for _,e1 := range edges {
a,b := e1[0],e1[1]
if parent[b]!=a { a,b = b,a }
for _,e2 := range edges {
if e1[0]==e2[0] && e1[1]==e2[1] { continue }
c,d := e2[0],e2[1]
if parent[d]!=c { c,d = d,c }
var x,y,z int
if isAncestor(b,d) {
x = xorv[d]; y = xorv[b]^xorv[d]; z = total^xorv[b]
} else if isAncestor(d,b) {
x = xorv[b]; y = xorv[d]^xorv[b]; z = total^xorv[d]
} else {
x = xorv[b]; y = xorv[d]; z = total^xorv[b]^xorv[d]
}
mx := x; if y>mx { mx=y }; if z>mx { mx=z }
mn := x; if y<mn { mn=y }; if z<mn { mn=z }
if mx-mn < res { res = mx-mn }
}
}
return res
}
Java
class Solution {
public 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[] xorv = new int[n], parent = new int[n];
Arrays.fill(parent,-1);
dfs(0,-1,nums,g,xorv,parent);
int total = xorv[0], res = Integer.MAX_VALUE;
for (int[] e1 : edges) {
int a=e1[0],b=e1[1]; if (parent[b]!=a) { int t=a;a=b;b=t; }
for (int[] e2 : edges) {
if (e1==e2) continue;
int c=e2[0],d=e2[1]; if (parent[d]!=c) { int t=c;c=d;d=t; }
int x,y,z;
if (isAncestor(b,d,parent)) {
x=xorv[d]; y=xorv[b]^xorv[d]; z=total^xorv[b];
} else if (isAncestor(d,b,parent)) {
x=xorv[b]; y=xorv[d]^xorv[b]; z=total^xorv[d];
} else {
x=xorv[b]; y=xorv[d]; z=total^xorv[b]^xorv[d];
}
int mx=Math.max(x,Math.max(y,z)), mn=Math.min(x,Math.min(y,z));
res=Math.min(res,mx-mn);
}
}
return res;
}
void dfs(int u,int p,int[] nums,List<Integer>[] g,int[] xorv,int[] parent) {
xorv[u]=nums[u]; parent[u]=p;
for (int v : g[u]) if (v!=p) { dfs(v,u,nums,g,xorv,parent); xorv[u]^=xorv[v]; }
}
boolean isAncestor(int u,int v,int[] parent) {
while (v!=-1) { if (v==u) return true; v=parent[v]; }
return false;
}
}
Kotlin
class Solution {
fun minimumScore(nums: IntArray, edges: Array<IntArray>): Int {
val n = nums.size
val g = Array(n){mutableListOf<Int>()}
for (e in edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]) }
val xorv = IntArray(n); val parent = IntArray(n){-1}
fun dfs(u:Int,p:Int) {
xorv[u]=nums[u]; parent[u]=p
for (v in g[u]) if (v!=p) { dfs(v,u); xorv[u]=xorv[u] xor xorv[v] }
}
dfs(0,-1)
val total = xorv[0]
var res = Int.MAX_VALUE
fun isAncestor(u:Int,v:Int):Boolean {
var vv=v; while (vv!=-1) { if (vv==u) return true; vv=parent[vv] }; return false
}
for (e1 in edges) {
var a=e1[0]; var b=e1[1]; if (parent[b]!=a) { val t=a;a=b;b=t }
for (e2 in edges) {
if (e1.contentEquals(e2)) continue
var c=e2[0]; var d=e2[1]; if (parent[d]!=c) { val t=c;c=d;d=t }
val (x,y,z) = if (isAncestor(b,d)) {
Triple(xorv[d], xorv[b] xor xorv[d], total xor xorv[b])
} else if (isAncestor(d,b)) {
Triple(xorv[b], xorv[d] xor xorv[b], total xor xorv[d])
} else {
Triple(xorv[b], xorv[d], total xor xorv[b] xor xorv[d])
}
val mx = maxOf(x,y,z); val mn = minOf(x,y,z)
res = minOf(res, mx-mn)
}
}
return res
}
}
Python
class Solution:
def minimumScore(self, nums: list[int], edges: list[list[int]]) -> int:
n = len(nums)
g = [[] for _ in range(n)]
for a,b in edges:
g[a].append(b); g[b].append(a)
xorv = [0]*n; parent = [-1]*n
def dfs(u,p):
xorv[u]=nums[u]; parent[u]=p
for v in g[u]:
if v!=p:
dfs(v,u); xorv[u]^=xorv[v]
dfs(0,-1)
total = xorv[0]; res = float('inf')
def isAncestor(u,v):
while v!=-1:
if v==u: return True
v=parent[v]
return False
for a,b in edges:
if parent[b]!=a: a,b=b,a
for c,d in edges:
if [a,b]==[c,d]: continue
if parent[d]!=c: c,d=d,c
if isAncestor(b,d):
x = xorv[d]; y = xorv[b]^xorv[d]; z = total^xorv[b]
elif isAncestor(d,b):
x = xorv[b]; y = xorv[d]^xorv[b]; z = total^xorv[d]
else:
x = xorv[b]; y = xorv[d]; z = total^xorv[b]^xorv[d]
mx = max(x,y,z); mn = min(x,y,z)
res = min(res, mx-mn)
return res
Rust
impl Solution {
pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
let n = nums.len();
let mut g = vec![vec![]; n];
for e in &edges { g[e[0]].push(e[1]); g[e[1]].push(e[0]); }
let mut xorv = vec![0;n]; let mut parent = vec![-1;n];
fn dfs(u:usize,p:usize,nums:&[i32],g:&[Vec<usize>],xorv:&mut [i32],parent:&mut [isize]) {
xorv[u]=nums[u]; parent[u]=p as isize;
for &v in &g[u] { if v!=p { dfs(v,u,nums,g,xorv,parent); xorv[u]^=xorv[v]; } }
}
dfs(0,usize::MAX,&nums,&g,&mut xorv,&mut parent);
let total = xorv[0]; let mut res = i32::MAX;
fn is_ancestor(u:usize,v:usize,parent:&[isize])->bool {
let mut vv=v as isize; while vv!=-1 { if vv==u as isize { return true; } vv=parent[vv as usize]; } false
}
for e1 in &edges {
let (mut a,mut b) = (e1[0],e1[1]); if parent[b]!=a as isize { std::mem::swap(&mut a,&mut b); }
for e2 in &edges {
if e1==e2 { continue; }
let (mut c,mut d) = (e2[0],e2[1]); if parent[d]!=c as isize { std::mem::swap(&mut c,&mut d); }
let (x,y,z) = if is_ancestor(b,d,&parent) {
(xorv[d], xorv[b]^xorv[d], total^xorv[b])
} else if is_ancestor(d,b,&parent) {
(xorv[b], xorv[d]^xorv[b], total^xorv[d])
} else {
(xorv[b], xorv[d], total^xorv[b]^xorv[d])
};
let mx = x.max(y).max(z); let mn = x.min(y).min(z);
res = res.min(mx-mn);
}
}
res
}
}
TypeScript
class Solution {
minimumScore(nums: number[], edges: number[][]): number {
const n = nums.length;
const g: number[][] = Array.from({length:n},()=>[]);
for (const [a,b] of edges) { g[a].push(b); g[b].push(a); }
const xorv = Array(n).fill(0), parent = Array(n).fill(-1);
function dfs(u:number,p:number) {
xorv[u]=nums[u]; parent[u]=p;
for (const v of g[u]) if (v!=p) { dfs(v,u); xorv[u]^=xorv[v]; }
}
dfs(0,-1);
const total = xorv[0]; let res = Infinity;
function isAncestor(u:number,v:number):boolean {
while (v!=-1) { if (v==u) return true; v=parent[v]; } return false;
}
for (const [a0,b0] of edges) {
let a=a0,b=b0; if (parent[b]!=a) [a,b]=[b,a];
for (const [c0,d0] of edges) {
if (a==c0 && b==d0) continue;
let c=c0,d=d0; if (parent[d]!=c) [c,d]=[d,c];
let x,y,z;
if (isAncestor(b,d)) {
x=xorv[d]; y=xorv[b]^xorv[d]; z=total^xorv[b];
} else if (isAncestor(d,b)) {
x=xorv[b]; y=xorv[d]^xorv[b]; z=total^xorv[d];
} else {
x=xorv[b]; y=xorv[d]; z=total^xorv[b]^xorv[d];
}
const mx = Math.max(x,y,z), mn = Math.min(x,y,z);
res = Math.min(res, mx-mn);
}
}
return res;
}
}
Complexity
- ⏰ Time complexity:
O(n^2)— For all pairs of edges. - 🧺 Space complexity:
O(n)— For tree and subtree XORs.
Method 2 – Single DFS with Entry/Exit Times
Intuition
By using a single DFS traversal, we can record entry and exit times for each node, which allows us to quickly determine ancestor-descendant relationships. We also compute the XOR of each subtree during this traversal. This structure enables us to efficiently enumerate all valid ways to split the tree by removing two edges and calculate the resulting component XORs.
Approach
- Perform a DFS from the root, recording for each node its entry (
in[x]) and exit (out[x]) times, and the XOR of its subtree (sum[x]). - For every pair of non-root nodes
uandv, consider removing the edge to their parent for each. - Use the entry/exit times to check if one node is an ancestor of the other, and compute the three component XORs accordingly:
- If
uis ancestor ofv: parts aresum[0]⊕sum[u],sum[u]⊕sum[v],sum[v]. - If
vis ancestor ofu: parts aresum[0]⊕sum[v],sum[v]⊕sum[u],sum[u]. - Otherwise: parts are
sum[0]⊕sum[u]⊕sum[v],sum[u],sum[v].
- If
- Track and return the minimum score found.
Code
C++
#include <vector>
#include <algorithm>
class Solution {
public:
int minimumScore(std::vector<int>& nums, std::vector<std::vector<int>>& edges) {
int n = nums.size();
std::vector<std::vector<int>> g(n);
for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
std::vector<int> sum(n), in(n), out(n);
int time = 0;
std::function<void(int,int)> dfs = [&](int u, int p) {
in[u] = time++;
sum[u] = nums[u];
for (int v : g[u]) if (v != p) { dfs(v, u); sum[u] ^= sum[v]; }
out[u] = time;
};
dfs(0, -1);
int res = INT_MAX;
for (int u = 1; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
if (in[v] > in[u] && in[v] < out[u]) {
res = std::min(res, calc(sum[0]^sum[u], sum[u]^sum[v], sum[v]));
} else if (in[u] > in[v] && in[u] < out[v]) {
res = std::min(res, calc(sum[0]^sum[v], sum[v]^sum[u], sum[u]));
} else {
res = std::min(res, calc(sum[0]^sum[u]^sum[v], sum[u], sum[v]));
}
}
}
return res;
}
int calc(int a, int b, int c) {
return std::max({a, b, c}) - std::min({a, b, c});
}
};
Go
func minimumScore(nums []int, edges [][]int) int {
n := len(nums)
g := make([][]int, n)
for _, e := range edges {
g[e[0]] = append(g[e[0]], e[1])
g[e[1]] = append(g[e[1]], e[0])
}
sum := make([]int, n)
in := make([]int, n)
out := make([]int, n)
time := 0
var dfs func(int, int)
dfs = func(u, p int) {
in[u] = time; time++
sum[u] = nums[u]
for _, v := range g[u] {
if v != p {
dfs(v, u)
sum[u] ^= sum[v]
}
}
out[u] = time
}
dfs(0, -1)
res := 1<<30
calc := func(a, b, c int) int {
mx, mn := a, a
if b > mx { mx = b }; if c > mx { mx = c }
if b < mn { mn = b }; if c < mn { mn = c }
return mx - mn
}
for u := 1; u < n; u++ {
for v := u + 1; v < n; v++ {
if in[v] > in[u] && in[v] < out[u] {
res = min(res, calc(sum[0]^sum[u], sum[u]^sum[v], sum[v]))
} else if in[u] > in[v] && in[u] < out[v] {
res = min(res, calc(sum[0]^sum[v], sum[v]^sum[u], sum[u]))
} else {
res = min(res, calc(sum[0]^sum[u]^sum[v], sum[u], sum[v]))
}
}
}
return res
}
func min(a, b int) int { if a < b { return a }; return b }
Java
class Solution {
public 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[] sum = new int[n], in = new int[n], out = new int[n], cnt = {0};
dfs(0, -1, nums, adj, sum, in, out, cnt);
int res = Integer.MAX_VALUE;
for (int u = 1; u < n; u++) {
for (int v = u + 1; v < n; v++) {
if (in[v] > in[u] && in[v] < out[u]) {
res = Math.min(res, calc(sum[0]^sum[u], sum[u]^sum[v], sum[v]));
} else if (in[u] > in[v] && in[u] < out[v]) {
res = Math.min(res, calc(sum[0]^sum[v], sum[v]^sum[u], sum[u]));
} else {
res = Math.min(res, calc(sum[0]^sum[u]^sum[v], sum[u], sum[v]));
}
}
}
return res;
}
private int calc(int a, int b, int c) {
return Math.max(a, Math.max(b, c)) - Math.min(a, Math.min(b, c));
}
private void dfs(int x, int fa, int[] nums, List<List<Integer>> adj, int[] sum, int[] in, int[] out, int[] cnt) {
in[x] = cnt[0]++;
sum[x] = nums[x];
for (int y : adj.get(x)) {
if (y == fa) continue;
dfs(y, x, nums, adj, sum, in, out, cnt);
sum[x] ^= sum[y];
}
out[x] = cnt[0];
}
}
Kotlin
class Solution {
fun minimumScore(nums: IntArray, edges: Array<IntArray>): Int {
val n = nums.size
val g = Array(n) { mutableListOf<Int>() }
for (e in edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]) }
val sum = IntArray(n); val inT = IntArray(n); val outT = IntArray(n)
var time = 0
fun dfs(u: Int, p: Int) {
inT[u] = time++
sum[u] = nums[u]
for (v in g[u]) if (v != p) { dfs(v, u); sum[u] = sum[u] xor sum[v] }
outT[u] = time
}
dfs(0, -1)
var res = Int.MAX_VALUE
fun calc(a: Int, b: Int, c: Int) = maxOf(a, b, c) - minOf(a, b, c)
for (u in 1 until n) {
for (v in u + 1 until n) {
if (inT[v] > inT[u] && inT[v] < outT[u]) {
res = minOf(res, calc(sum[0] xor sum[u], sum[u] xor sum[v], sum[v]))
} else if (inT[u] > inT[v] && inT[u] < outT[v]) {
res = minOf(res, calc(sum[0] xor sum[v], sum[v] xor sum[u], sum[u]))
} else {
res = minOf(res, calc(sum[0] xor sum[u] xor sum[v], sum[u], sum[v]))
}
}
}
return res
}
}
Python
class Solution:
def minimumScore(self, nums: list[int], edges: list[list[int]]) -> int:
n = len(nums)
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b); g[b].append(a)
sumv = [0] * n; tin = [0] * n; tout = [0] * n; time = [0]
def dfs(u, p):
tin[u] = time[0]; time[0] += 1
sumv[u] = nums[u]
for v in g[u]:
if v != p:
dfs(v, u)
sumv[u] ^= sumv[v]
tout[u] = time[0]
dfs(0, -1)
res = float('inf')
def calc(a, b, c): return max(a, b, c) - min(a, b, c)
for u in range(1, n):
for v in range(u + 1, n):
if tin[v] > tin[u] and tin[v] < tout[u]:
res = min(res, calc(sumv[0] ^ sumv[u], sumv[u] ^ sumv[v], sumv[v]))
elif tin[u] > tin[v] and tin[u] < tout[v]:
res = min(res, calc(sumv[0] ^ sumv[v], sumv[v] ^ sumv[u], sumv[u]))
else:
res = min(res, calc(sumv[0] ^ sumv[u] ^ sumv[v], sumv[u], sumv[v]))
return res
Rust
impl Solution {
pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
let n = nums.len();
let mut g = vec![vec![]; n];
for e in &edges { g[e[0]].push(e[1]); g[e[1]].push(e[0]); }
let mut sum = vec![0; n]; let mut tin = vec![0; n]; let mut tout = vec![0; n];
let mut time = 0;
fn dfs(u: usize, p: isize, g: &Vec<Vec<usize>>, nums: &Vec<i32>, sum: &mut Vec<i32>, tin: &mut Vec<usize>, tout: &mut Vec<usize>, time: &mut usize) {
tin[u] = *time; *time += 1;
sum[u] = nums[u];
for &v in &g[u] {
if v as isize != p {
dfs(v, u as isize, g, nums, sum, tin, tout, time);
sum[u] ^= sum[v];
}
}
tout[u] = *time;
}
dfs(0, -1, &g, &nums, &mut sum, &mut tin, &mut tout, &mut time);
let mut res = i32::MAX;
for u in 1..n {
for v in (u + 1)..n {
let (a, b, c) = if tin[v] > tin[u] && tin[v] < tout[u] {
(sum[0] ^ sum[u], sum[u] ^ sum[v], sum[v])
} else if tin[u] > tin[v] && tin[u] < tout[v] {
(sum[0] ^ sum[v], sum[v] ^ sum[u], sum[u])
} else {
(sum[0] ^ sum[u] ^ sum[v], sum[u], sum[v])
};
let mx = a.max(b).max(c); let mn = a.min(b).min(c);
res = res.min(mx - mn);
}
}
res
}
}
TypeScript
class Solution {
minimumScore(nums: number[], edges: number[][]): number {
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) { g[a].push(b); g[b].push(a); }
const sum = Array(n).fill(0), tin = Array(n).fill(0), tout = Array(n).fill(0);
let time = 0;
function dfs(u: number, p: number) {
tin[u] = time++;
sum[u] = nums[u];
for (const v of g[u]) if (v !== p) { dfs(v, u); sum[u] ^= sum[v]; }
tout[u] = time;
}
dfs(0, -1);
let res = Infinity;
function calc(a: number, b: number, c: number) { return Math.max(a, b, c) - Math.min(a, b, c); }
for (let u = 1; u < n; ++u) {
for (let v = u + 1; v < n; ++v) {
if (tin[v] > tin[u] && tin[v] < tout[u]) {
res = Math.min(res, calc(sum[0] ^ sum[u], sum[u] ^ sum[v], sum[v]));
} else if (tin[u] > tin[v] && tin[u] < tout[v]) {
res = Math.min(res, calc(sum[0] ^ sum[v], sum[v] ^ sum[u], sum[u]));
} else {
res = Math.min(res, calc(sum[0] ^ sum[u] ^ sum[v], sum[u], sum[v]));
}
}
}
return res;
}
}
Complexity
- ⏰ Time complexity:
O(n^2)— For all pairs of non-root nodes. - 🧺 Space complexity:
O(n)— For tree, entry/exit times, and subtree XORs.