Minimum Score After Removals on a Tree
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 i^th 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.
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
9Removing the shown pair of edges gives component XOR values 10, 1, and 5, so the score is 10 - 1 = 9, and no smaller score is possible.
Example 2
Input
nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]Output
0Removing the shown pair of edges gives component XOR values 0, 0, and 0, so the minimum possible score is 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.
Asked at 4 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.