Minimum Score After Removals on a Tree

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 are 4 ^ 5 ^ 7 = _**6**_, 1 ^ 9 = _**8**_, and 3 ^ 3 ^ 3 = _**3**_. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 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

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


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.length
3 <= n <= 1000
1 <= nums[i] <= 10^8
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents 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

 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
34
35
36
37
38
39
40
41
42
43
44


#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;
    }
};

 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
34
35
36
37
38
39
40
41
42
43
44


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
}

 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
34
35
36
37
38
39
40


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;
    }
}

 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
34
35


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
    }
}

 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:
        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

 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
34


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
    }
}

 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
34
35


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 u and v, 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 u is ancestor of v: parts are sum[0]⊕sum[u], sum[u]⊕sum[v], sum[v].
- If v is ancestor of u: parts are sum[0]⊕sum[v], sum[v]⊕sum[u], sum[u].
- Otherwise: parts are sum[0]⊕sum[u]⊕sum[v], sum[u], sum[v].
Track and return the minimum score found.

Code

 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
34
35


#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});
    }
};

 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
34
35
36
37
38
39
40
41
42
43
44
45


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 }

 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
34
35
36


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];
    }
}

 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


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
    }
}

 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


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

 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
34
35
36


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
    }
}

 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


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.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – DFS Subtree XORs + Edge Removal Simulation#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Single DFS with Entry/Exit Times#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Constraints

Solution

Method 1 – DFS Subtree XORs + Edge Removal Simulation

Intuition

Approach

Code

Complexity

Method 2 – Single DFS with Entry/Exit Times

Intuition

Approach

Code

Complexity