# Minimum Score After Removals on a Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-score-after-removals-on-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/minimum-score-after-removals-on-a-tree
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, 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:

1. Get the XOR of all the values of the nodes for **each** of the three components respectively.
2. 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 _the **minimum** score of any possible pair of edge removals on the given tree_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-score-after-removals-on-a-tree/image0.png) 

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

![](https://assets.glich.co/dsa/minimum-score-after-removals-on-a-tree/image1.png) 

**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] <= 108`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* `edges` represents a valid tree.

# Approaches
## Brute Force with Graph Traversal
The most straightforward approach is to simulate the process directly. We can iterate through every possible pair of distinct edges in the tree. For each pair, we conceptually remove them, which results in three disconnected components. Then, we traverse each component to find all its nodes and calculate the XOR sum of their values. Finally, we compute the score for this pair of removals and keep track of the minimum score found across all pairs.
**Time:** O(N^3), where N is the number of nodes. There are O(N^2) pairs of edges. For each pair, we build a temporary graph and traverse it, which takes O(N) time. This results in a total time complexity of O(N^2 * N) = O(N^3). · **Space:** O(N) to store the temporary adjacency list and the visited array for the graph traversal.
**Pros:** Conceptually simple and easy to understand.; Directly follows the problem description.
**Cons:** Highly inefficient due to the cubic time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs (N=1000).
### Explanation
This method involves a nested loop to select two distinct edges to remove. For each pair of selected edges, we construct a new graph representation (e.g., an adjacency list) without these two edges. The resulting graph will consist of three separate connected components.

To find these components and their XOR sums, we can use a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). We use a `visited` array to ensure we process each node only once. We iterate through all nodes from `0` to `n-1`. If a node hasn't been visited, we start a traversal from it, which will explore one entire component. During the traversal, we accumulate the XOR sum of the values of all nodes in that component. After three such traversals, we will have the XOR sums for the three components.

- **Algorithm:**
 1. Iterate through all pairs of distinct edges `(e1, e2)` from the input `edges` array.
 2. For each pair, create a temporary adjacency list representing the tree with `e1` and `e2` removed.
 3. Initialize a `visited` array of size `n` to `false` and a list to store component XOR sums.
 4. Iterate from node `i = 0` to `n-1`:
    - If `i` is not visited, it means we've found a new component.
    - Start a graph traversal (DFS or BFS) from `i`.
    - During the traversal, mark nodes as visited and calculate the XOR sum of all node values in this component.
    - Add the calculated XOR sum to our list.
 5. Once three component XOR sums are found, calculate the score: `max_xor - min_xor`.
 6. Update the global minimum score with the current score if it's smaller.
 7. After checking all pairs of edges, return the global minimum score.

```java
import java.util.*;

class Solution {
    public int minimumScore(int[] nums, int[][] edges) {
        int n = nums.length;
        int minScore = Integer.MAX_VALUE;

        for (int i = 0; i < edges.length; i++) {
            for (int j = i + 1; j < edges.length; j++) {
                // Build a temporary graph with the two edges removed
                List<Integer>[] tempAdj = new ArrayList[n];
                for (int k = 0; k < n; k++) {
                    tempAdj[k] = new ArrayList<>();
                }
                for (int k = 0; k < edges.length; k++) {
                    if (k == i || k == j) continue;
                    int u = edges[k][0];
                    int v = edges[k][1];
                    tempAdj[u].add(v);
                    tempAdj[v].add(u);
                }

                // Find the three components and their XOR sums
                List<Integer> xorSums = new ArrayList<>();
                boolean[] visited = new boolean[n];
                for (int k = 0; k < n; k++) {
                    if (!visited[k]) {
                        xorSums.add(findComponentXor(k, tempAdj, nums, visited));
                    }
                }
                
                // Calculate score
                if (xorSums.size() == 3) {
                    int maxVal = Collections.max(xorSums);
                    int minVal = Collections.min(xorSums);
                    minScore = Math.min(minScore, maxVal - minVal);
                }
            }
        }
        return minScore;
    }

    private int findComponentXor(int u, List<Integer>[] adj, int[] nums, boolean[] visited) {
        visited[u] = true;
        int xorSum = nums[u];
        for (int v : adj[u]) {
            if (!visited[v]) {
                xorSum ^= findComponentXor(v, adj, nums, visited);
            }
        }
        return xorSum;
    }
}
```
### Algorithm
- Iterate through all pairs of distinct edges `(e1, e2)` from the input `edges` array.
- For each pair, create a temporary adjacency list representing the tree with `e1` and `e2` removed.
- Initialize a `visited` array of size `n` to `false` and a list to store component XOR sums.
- Iterate from node `i = 0` to `n-1`:
    - If `i` is not visited, it means we've found a new component.
    - Start a graph traversal (DFS or BFS) from `i`.
    - During the traversal, mark nodes as visited and calculate the XOR sum of all node values in this component.
    - Add the calculated XOR sum to our list.
- Once three component XOR sums are found, calculate the score: `max_xor - min_xor`.
- Update the global minimum score with the current score if it's smaller.
- After checking all pairs of edges, return the global minimum score.

## Pre-computation with DFS
A more efficient approach avoids re-computing component information from scratch for every pair of edges. We can pre-calculate essential information about the tree structure using a single Depth-First Search (DFS). By rooting the tree arbitrarily (e.g., at node 0), we can compute the XOR sum of every possible subtree that can be formed by a single edge cut. With this pre-computed data, we can then iterate through all pairs of edge cuts and determine the XOR sums of the three resulting components in constant time.
**Time:** O(N^2), where N is the number of nodes. The initial DFS for pre-computation takes O(N) time. The main part is the nested loop that iterates through O(N^2) pairs of nodes. Inside the loop, all operations (ancestry check, XOR calculations) take O(1) time. Thus, the total time complexity is dominated by the nested loops. · **Space:** O(N) to store the adjacency list, `subtreeXor` array, and DFS traversal time arrays.
**Pros:** Significantly more efficient than the brute-force approach.; Passes within the time limits for the given constraints.; Demonstrates efficient use of tree traversal properties.
**Cons:** Requires a deeper understanding of tree algorithms and properties like subtree aggregates and ancestry checks.; The logic is more complex to implement correctly compared to the naive approach.
### Explanation
The core idea is to perform a single DFS traversal from an arbitrary root (e.g., node 0) to gather information. During this DFS, we can compute:
1. The XOR sum of the subtree rooted at each node `u` (`subtreeXor[u]`)
2. The parent of each node.
3. The DFS start and end times for each node, which allows for O(1) ancestry checks (`isAncestor(u, v)`).

After the pre-computation, we iterate through all pairs of nodes `i` and `j` (where `i, j != 0`). Removing the edges `(parent[i], i)` and `(parent[j], j)` simulates the two cuts. There are two main scenarios for the relationship between these cuts:

- **Case 1: Nested Subtrees.** One node is an ancestor of the other (e.g., `i` is an ancestor of `j`). The three components are the subtree at `j`, the nodes in `i`'s subtree but not `j`'s, and the rest of the tree. Their XOR sums can be calculated as: `subtreeXor[j]`, `subtreeXor[i] ^ subtreeXor[j]`, and `totalXor ^ subtreeXor[i]`.
- **Case 2: Disjoint Subtrees.** Neither node is an ancestor of the other. The three components are the subtree at `i`, the subtree at `j`, and the rest of the tree. Their XOR sums are: `subtreeXor[i]`, `subtreeXor[j]`, and `totalXor ^ subtreeXor[i] ^ subtreeXor[j]`.

By iterating through all `O(N^2)` pairs of nodes and performing these O(1) calculations, we can find the minimum score efficiently.

- **Algorithm:**
 1. Build an adjacency list for the tree.
 2. Calculate the `totalXor` of all node values.
 3. Perform a single DFS traversal starting from root 0 to compute `subtreeXor`, `startTime`, and `endTime` for every node.
 4. Initialize `minScore` to a very large value.
 5. Iterate through all pairs of nodes `(i, j)` from `1` to `n-1` with `i < j`.
    - Let `xor_i = subtreeXor[i]` and `xor_j = subtreeXor[j]`.
    - Use `startTime` and `endTime` to check if `i` is an ancestor of `j` or vice-versa.
    - Based on the ancestry relationship, calculate the three component XORs (`x1, x2, x3`) using the formulas described above.
    - Compute the score: `max(x1, x2, x3) - min(x1, x2, x3)`.
    - Update `minScore`.
 6. Return `minScore`.

```java
import java.util.*;

class Solution {
    List<Integer>[] adj;
    int[] nums;
    int[] subtreeXor;
    int[] startTime, endTime;
    int timer;
    int minScore = Integer.MAX_VALUE;
    int totalXor = 0;

    public int minimumScore(int[] nums, int[][] edges) {
        int n = nums.length;
        this.nums = nums;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            totalXor ^= nums[i];
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        this.subtreeXor = new int[n];
        this.startTime = new int[n];
        this.endTime = new int[n];
        this.timer = 0;

        dfs(0, -1);

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xor_i = subtreeXor[i];
                int xor_j = subtreeXor[j];
                int x1, x2, x3;

                if (isAncestor(i, j)) { // i is an ancestor of j
                    x1 = xor_j;
                    x2 = xor_i ^ xor_j;
                    x3 = totalXor ^ xor_i;
                } else if (isAncestor(j, i)) { // j is an ancestor of i
                    x1 = xor_i;
                    x2 = xor_j ^ xor_i;
                    x3 = totalXor ^ xor_j;
                } else { // disjoint subtrees
                    x1 = xor_i;
                    x2 = xor_j;
                    x3 = totalXor ^ xor_i ^ xor_j;
                }

                int maxVal = Math.max(x1, Math.max(x2, x3));
                int minVal = Math.min(x1, Math.min(x2, x3));
                minScore = Math.min(minScore, maxVal - minVal);
            }
        }

        return minScore;
    }

    private void dfs(int u, int p) {
        startTime[u] = timer++;
        subtreeXor[u] = nums[u];
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u);
                subtreeXor[u] ^= subtreeXor[v];
            }
        }
        endTime[u] = timer++;
    }

    private boolean isAncestor(int u, int v) {
        return startTime[u] < startTime[v] && endTime[u] > endTime[v];
    }
}
```
### Algorithm
- Build an adjacency list for the tree.
- Calculate the `totalXor` of all node values.
- Perform a single DFS traversal starting from root 0 to compute `subtreeXor`, `startTime`, and `endTime` for every node.
- Initialize `minScore` to a very large value.
- Iterate through all pairs of nodes `(i, j)` from `1` to `n-1` with `i < j`.
    - Let `xor_i = subtreeXor[i]` and `xor_j = subtreeXor[j]`.
    - Use `startTime` and `endTime` to check if `i` is an ancestor of `j` or vice-versa.
    - Based on the ancestry relationship, calculate the three component XORs (`x1, x2, x3`) using the formulas described above.
    - Compute the score: `max(x1, x2, x3) - min(x1, x2, x3)`.
    - Update `minScore`.
- Return `minScore`.

# Solutions
### Java

```java
class Solution { private int s ; private int s1 ; private int n ; private int ans = Integer . MAX_VALUE ; private int [] nums ; private List < Integer >[] g ; public int minimumScore ( int [] nums , int [][] edges ) { n = nums . length ; g = new List [ n ]; this . nums = nums ; Arrays . setAll ( g , k -> new ArrayList <>()); for ( int [] e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. add ( b ); g [ b ]. add ( a ); } for ( int v : nums ) { s ^= v ; } for ( int i = 0 ; i < n ; ++ i ) { for ( int j : g [ i ]) { s1 = dfs ( i , - 1 , j ); dfs2 ( i , - 1 , j ); } } return ans ; } private int dfs ( int i , int fa , int x ) { int res = nums [ i ]; for ( int j : g [ i ]) { if ( j != fa && j != x ) { res ^= dfs ( j , i , x ); } } return res ; } private int dfs2 ( int i , int fa , int x ) { int res = nums [ i ]; for ( int j : g [ i ]) { if ( j != fa && j != x ) { int a = dfs2 ( j , i , x ); res ^= a ; int b = s1 ^ a ; int c = s ^ s1 ; int t = Math . max ( Math . max ( a , b ), c ) - Math . min ( Math . min ( a , b ), c ); ans = Math . min ( ans , t ); } } return res ; } }
```

### CPP

```cpp
class Solution { public: vector < int > nums ; int s ; int s1 ; int n ; int ans = INT_MAX ; vector < vector < int >> g ; int minimumScore ( vector < int >& nums , vector < vector < int >>& edges ) { n = nums . size (); g . resize ( n , vector < int > ()); for ( auto & e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); } for ( int & v : nums ) s ^= v ; this -> nums = nums ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j : g [ i ]) { s1 = dfs ( i , - 1 , j ); dfs2 ( i , - 1 , j ); } } return ans ; } int dfs ( int i , int fa , int x ) { int res = nums [ i ]; for ( int j : g [ i ]) if ( j != fa && j != x ) res ^= dfs ( j , i , x ); return res ; } int dfs2 ( int i , int fa , int x ) { int res = nums [ i ]; for ( int j : g [ i ]) if ( j != fa && j != x ) { int a = dfs2 ( j , i , x ); res ^= a ; int b = s1 ^ a ; int c = s ^ s1 ; int t = max ( max ( a , b ), c ) - min ( min ( a , b ), c ); ans = min ( ans , t ); } return res ; } };
```

### Python

```python
class Solution : def minimumScore ( self , nums : List [ int ], edges : List [ List [ int ]]) -> int : def dfs ( i , fa , x ): res = nums [ i ] for j in g [ i ]: if j != fa and j != x : res ^= dfs ( j , i , x ) return res def dfs2 ( i , fa , x ): nonlocal s , s1 , ans res = nums [ i ] for j in g [ i ]: if j != fa and j != x : a = dfs2 ( j , i , x ) res ^= a b = s1 ^ a c = s ^ s1 t = max ( a , b , c ) - min ( a , b , c ) ans = min ( ans , t ) return res g = defaultdict ( list ) for a , b in edges : g [ a ]. append ( b ) g [ b ]. append ( a ) s = 0 for v in nums : s ^= v n = len ( nums ) ans = inf for i in range ( n ): for j in g [ i ]: s1 = dfs ( i , - 1 , j ) dfs2 ( i , - 1 , j ) return ans
```