Remove two edges from a tree to split it into three components, then minimize the difference between the largest and smallest component XOR values.
You are given an undirected tree with n nodes labeled from 0 to n - 1 and an integer array nums, where nums[i] is the value stored at node i.
You must remove exactly two different edges from the tree. This splits the tree into three connected components. For each component, compute the bitwise XOR of all node values inside it.
Let these three XOR values be a, b, and c. Your task is to minimize:
Return the minimum possible score.
A tree is a connected graph with no cycles.
Input Format
n: number of nodesnums: integer values for each nodeedges: list ofn - 1undirected edges of the tree
Output Format
- Return the minimum achievable score after removing exactly two edges.
Constraints
- The input graph is a tree.
- Exactly two edges must be removed.
- Node values are combined using bitwise XOR within each resulting component.
Example 1
Input
nums = [1,5,5,4,11]\nedges = [[0,1],[1,2],[1,3],[3,4]]
Output
9
Explanation
One optimal choice is removing edges [1,3] and [3,4]. The three components have XOR values 1, 0, and 11, so the score is 11 - 0 = 11. Another cut choice can produce a smaller score; the minimum possible score for this tree is 9.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.