Watch 10 video solutions for Minimum Score After Removals on a Tree, a hard level problem involving Array, Bit Manipulation, Tree. This walkthrough by codestorywithMIK has 9,720 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[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:
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:
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] <= 108edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges represents a valid tree.Problem Overview: You are given a tree where each node has a value. Remove two edges to split the tree into three components. For each component compute the XOR of node values, then minimize the difference between the maximum and minimum XOR values.
Approach 1: Brute Force with Optimizations (O(n^3) time, O(n) space)
The direct idea is to try every pair of edges to remove. Removing two edges splits the tree into three components, so you compute the XOR of each component and track the score max(x1, x2, x3) - min(x1, x2, x3). A DFS can compute XOR values for a component after temporarily removing edges. Since there are O(n^2) edge pairs and each component computation can take O(n), the total complexity becomes O(n^3). Some implementations reduce repeated work by caching subtree results or precomputing node values, but the approach is still expensive for large trees.
Approach 2: DFS with Subtree XOR Caching (O(n^2) time, O(n) space)
The optimized solution precomputes the XOR of every subtree using a single DFS. While traversing the tree, store each node's subtree XOR and maintain entry/exit times to determine ancestor relationships. The key observation: removing an edge corresponds to isolating a subtree. If you know subtree XOR values, you can derive the XOR of the remaining parts using simple XOR arithmetic.
For every pair of nodes representing removed edges, determine how their subtrees interact. There are three cases: one subtree inside another, the reverse nesting, or completely disjoint subtrees. Using ancestor checks from DFS timestamps, compute the three component XOR values in constant time. This reduces each pair evaluation to O(1), making the total runtime O(n^2) after a single DFS preprocessing step.
This approach relies heavily on Depth-First Search traversal and XOR properties from Bit Manipulation. Precomputing subtree information transforms repeated graph traversals into constant-time calculations.
Recommended for interviews: Interviewers expect the DFS + subtree XOR caching approach. The brute force method shows you understand the problem structure and component splitting. The optimized solution demonstrates stronger tree reasoning: precomputing subtree data, using ancestor checks, and applying XOR algebra to compute component values efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Component DFS | O(n^3) | O(n) | Conceptual baseline or when constraints are very small |
| Brute Force with Cached Subtree XOR | O(n^2) | O(n) | When subtree XOR values are precomputed to avoid repeated DFS |
| DFS with Subtree XOR + Ancestor Checks | O(n^2) | O(n) | Optimal interview solution for tree splitting problems |