2322. Minimum Score After Removals on a Tree Hard

1/**
2 * [2322] Minimum Score After Removals on a Tree
3 *
4 * There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
5 * 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.
6 * Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:
7 * <ol>
8 * 	Get the XOR of all the values of the nodes for each of the three components respectively.
9 * 	The difference between the largest XOR value and the smallest XOR value is the score of the pair.
10 * </ol>
11 * 
12 * 	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 = <u>6</u>, 1 ^ 9 = <u>8</u>, and 3 ^ 3 ^ 3 = <u>3</u>. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 3 = 5.
13 * 
14 * Return the minimum score of any possible pair of edge removals on the given tree.
15 *  
16 * Example 1:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png" style="width: 193px; height: 190px;" />
18 * Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
19 * Output: 9
20 * Explanation: The diagram above shows a way to make a pair of removals.
21 * - The 1^st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
22 * - The 2^nd component has node [0] with value [1]. Its XOR value is 1 = 1.
23 * - The 3^rd component has node [2] with value [5]. Its XOR value is 5 = 5.
24 * The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.
25 * It can be shown that no other pair of removals will obtain a smaller score than 9.
26 * 
27 * Example 2:
28 * <img alt="" src="https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png" style="width: 287px; height: 150px;" />
29 * Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
30 * Output: 0
31 * Explanation: The diagram above shows a way to make a pair of removals.
32 * - The 1^st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
33 * - The 2^nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
34 * - The 3^rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.
35 * The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.
36 * We cannot obtain a smaller score than 0.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	n == nums.length
42 * 	3 <= n <= 1000
43 * 	1 <= nums[i] <= 10^8
44 * 	edges.length == n - 1
45 * 	edges[i].length == 2
46 * 	0 <= ai, bi < n
47 * 	ai != bi
48 * 	edges represents a valid tree.
49 * 
50 */
51pub struct Solution {}
52
53// problem: https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/
54// discuss: https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
55
56// submission codes start here
57
58impl Solution {
59    pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
60        0
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_2322() {
72    }
73}
74