Welcome to Subscribe On Youtube
2322. Minimum Score After Removals on a Tree
Description
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:
- 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.
- For example, say the three components have the node values:
[4,5,7],[1,9], and[3,3,3]. The three XOR values are4 ^ 5 ^ 7 = 6,1 ^ 9 = 8, and3 ^ 3 ^ 3 = 3. The largest XOR value is8and the smallest XOR value is3. The score is then8 - 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 != biedgesrepresents a valid tree.
Solutions
-
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; } } -
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; } }; -
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 -
func minimumScore(nums []int, edges [][]int) int { n := len(nums) g := make([][]int, n) for _, e := range edges { a, b := e[0], e[1] g[a] = append(g[a], b) g[b] = append(g[b], a) } s := 0 for _, v := range nums { s ^= v } s1 := 0 ans := math.MaxInt32 var dfs func(int, int, int) int var dfs2 func(int, int, int) int dfs = func(i, fa, x int) int { res := nums[i] for _, j := range g[i] { if j != fa && j != x { res ^= dfs(j, i, x) } } return res } dfs2 = func(i, fa, x int) int { res := nums[i] for _, j := range g[i] { if j != fa && j != x { a := dfs2(j, i, x) res ^= a b := s1 ^ a c := s ^ s1 t := max(max(a, b), c) - min(min(a, b), c) ans = min(ans, t) } } return res } for i := 0; i < n; i++ { for _, j := range g[i] { s1 = dfs(i, -1, j) dfs2(i, -1, j) } } return ans } -
function minimumScore(nums: number[], edges: number[][]): number { const n = nums.length; const g: number[][] = Array.from({ length: n }, () => []); for (const [a, b] of edges) { g[a].push(b); g[b].push(a); } const s = nums.reduce((a, b) => a ^ b, 0); let s1 = 0; let ans = Number.MAX_SAFE_INTEGER; function dfs(i: number, fa: number): number { let res = nums[i]; for (const j of g[i]) { if (j !== fa) { res ^= dfs(j, i); } } return res; } function dfs2(i: number, fa: number): number { let res = nums[i]; for (const j of g[i]) { if (j !== fa) { const s2 = dfs2(j, i); res ^= s2; const mx = Math.max(s ^ s1, s2, s1 ^ s2); const mn = Math.min(s ^ s1, s2, s1 ^ s2); ans = Math.min(ans, mx - mn); } } return res; } for (let i = 0; i < n; ++i) { for (const j of g[i]) { s1 = dfs(i, j); dfs2(i, j); } } return ans; } -
impl Solution { pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 { let n = nums.len(); let mut g = vec![vec![]; n]; for e in edges.iter() { let a = e[0] as usize; let b = e[1] as usize; g[a].push(b); g[b].push(a); } let mut s1 = 0; let mut ans = i32::MAX; let s = nums.iter().fold(0, |acc, &x| acc ^ x); fn dfs(i: usize, fa: usize, g: &Vec<Vec<usize>>, nums: &Vec<i32>) -> i32 { let mut res = nums[i]; for &j in &g[i] { if j != fa { res ^= dfs(j, i, g, nums); } } res } fn dfs2( i: usize, fa: usize, g: &Vec<Vec<usize>>, nums: &Vec<i32>, s: i32, s1: i32, ans: &mut i32, ) -> i32 { let mut res = nums[i]; for &j in &g[i] { if j != fa { let s2 = dfs2(j, i, g, nums, s, s1, ans); res ^= s2; let mx = (s ^ s1).max(s2).max(s1 ^ s2); let mn = (s ^ s1).min(s2).min(s1 ^ s2); *ans = (*ans).min(mx - mn); } } res } for i in 0..n { for &j in &g[i] { s1 = dfs(i, j, &g, &nums); dfs2(i, j, &g, &nums, s, s1, &mut ans); } } ans } } -
public class Solution { public int MinimumScore(int[] nums, int[][] edges) { int n = nums.Length; List<int>[] g = new List<int>[n]; for (int i = 0; i < n; i++) { g[i] = new List<int>(); } foreach (var e in edges) { int a = e[0], b = e[1]; g[a].Add(b); g[b].Add(a); } int s = 0; foreach (int x in nums) { s ^= x; } int ans = int.MaxValue; int s1 = 0; int Dfs(int i, int fa) { int res = nums[i]; foreach (int j in g[i]) { if (j != fa) { res ^= Dfs(j, i); } } return res; } int Dfs2(int i, int fa) { int res = nums[i]; foreach (int j in g[i]) { if (j != fa) { int s2 = Dfs2(j, i); res ^= s2; int mx = Math.Max(Math.Max(s ^ s1, s2), s1 ^ s2); int mn = Math.Min(Math.Min(s ^ s1, s2), s1 ^ s2); ans = Math.Min(ans, mx - mn); } } return res; } for (int i = 0; i < n; ++i) { foreach (int j in g[i]) { s1 = Dfs(i, j); Dfs2(i, j); } } return ans; } }