![[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Minimum-Score-After-Removals-on-a-Tree-LeetCode-Contest-Problem.png "[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem")
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 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:
![[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem](https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png "[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem")
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:
![[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem](https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png "[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem")
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.
Solution
int dp[1000] = {}, last[1000] = {};
int dfs(vector<int>& n, vector<vector<int>> &al, int i, int p, int &ids) {
int res = n[i];
for (auto j : al[i])
if (j != p) {
int id = ids++;
dp[id] = dfs(n, al, j, i, ids);
last[id] = ids;
res ^= dp[id];
}
return res;
}
int minimumScore(vector<int>& n, vector<vector<int>>& edges) {
int ids = 0, res = INT_MAX;
vector<vector<int>> al(n.size());
for (auto &e : edges) {
al[e[0]].push_back(e[1]);
al[e[1]].push_back(e[0]);
}
int all = dfs(n, al, 0, -1, ids);
for (int i = 0; i < edges.size(); ++i)
for (int j = i + 1; j < edges.size(); ++j) {
int p1 = j < last[i] ? all ^ dp[i] : all ^ dp[i] ^ dp[j];
int p2 = j < last[i] ? dp[i] ^ dp[j] : dp[i];
res = min(res, max({p1, p2, dp[j]}) - min({p1, p2, dp[j]}));
}
return res;
}
We can also memoise XOR for nodes, not edges. Each edge connects to a node, so it’s pretty much the same.
int dp[1000] = {}, last[1000] = {};
int dfs(vector<int>& n, vector<vector<int>> &al, int i, int p, int &ids) {
int id = ids++, res = n[i];
for (auto j : al[i])
if (j != p)
res ^= dfs(n, al, j, i, ids);
last[id] = ids;
return dp[id] = res;
}
int minimumScore(vector<int>& n, vector<vector<int>>& edges) {
int ids = 0, res = INT_MAX;
vector<vector<int>> al(n.size());
for (auto &e : edges) {
al[e[0]].push_back(e[1]);
al[e[1]].push_back(e[0]);
}
int all = dfs(n, al, 0, -1, ids);
for (int i = 1; i < n.size(); ++i)
for (int j = i + 1; j < n.size(); ++j) {
int p1 = j < last[i] ? all ^ dp[i] : all ^ dp[i] ^ dp[j];
int p2 = j < last[i] ? dp[i] ^ dp[j] : dp[i];
res = min(res, max({p1, p2, dp[j]}) - min({p1, p2, dp[j]}));
}
return res;
}class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
find = defaultdict(list)
for x, y in edges:
find[x].append(y)
find[y].append(x)
@cache
def get_xors_of_subtree(root, prev):
res = []
val = nums[root]
for y in find[root]:
if y != prev:
tmp = get_xors_of_subtree(y, root)
res.extend(tmp)
val ^= tmp[-1]
res.append(val)
return res
res = math.inf
for x, y in edges:
left_xors = get_xors_of_subtree(x, y)
right_xors = get_xors_of_subtree(y, x)
left_val = left_xors[-1]
right_val = right_xors[-1]
for l1 in left_xors[:-1]:
l2 = left_val ^ l1
res = min(res, max(l1, l2, right_val) - min(l1, l2, right_val))
for r1 in right_xors[:-1]:
r2 = right_val ^ r1
res = min(res, max(r1, r2, left_val) - min(r1, r2, left_val))
return resclass Solution {
int[] xors;
Map<Integer, List<Integer>> map = new HashMap<>();
Map<Integer, Set<Integer>> subTree = new HashMap<>();
public int minimumScore(int[] nums, int[][] edges) {
int total = 0;
int n = nums.length;
xors = new int[n];
for (int i = 0; i < nums.length; ++i) {
total = total ^ nums[i];
}
// System.out.println("total " + total);
for (var edge : edges) {
int u = edge[0];
int v = edge[1];
var list = map.getOrDefault(u, new ArrayList<>());
list.add(v);
map.put(u, list);
list = map.getOrDefault(v, new ArrayList<>());
list.add(u);
map.put(v, list);
}
go (0, -1, nums);
populateSubTree(0, -1);
// for (var entry : subTree.entrySet()) {
// System.out.println(entry.getKey() + "\t" + entry.getValue());
// }
int min = Integer.MAX_VALUE;
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int t1, t2, t3;
if (subTree.get(i).contains(j)) {
// i is the parent of j
t1 = xors[0] ^ xors[i];
t2 = xors[j];
t3 = xors[0] ^ t1 ^ t2;
// System.out.println("i=" + i + "\t" + "j=" + j);
// System.out.println(t1 + "\t" + t2 + "\t" + t3);
} else if (subTree.get(j).contains(i)) {
// j is the parent of i
t1 = xors[i];
t2 = xors[0] ^ xors[j];
t3 = xors[0] ^ t1 ^ t2;
} else {
t1 = xors[j];
t2 = xors[i];
t3 = xors[0] ^ t1 ^ t2;
}
int max_t = Math.max(Math.max(t1, t2), t3);
int min_t = Math.min(Math.min(t1, t2), t3);
min = Math.min(min, max_t - min_t);
}
}
return min;
}
Set<Integer> populateSubTree(int index, int p_index) {
Set<Integer> result = new HashSet<>();
result.add(index);
for (var node : map.getOrDefault(index, new ArrayList<>())) {
if (p_index != node) {
var childSet = populateSubTree(node, index);
result.addAll(childSet);
}
}
// System.out.println("Putting " + index + "\t" + result);
subTree.put(index, result);
return result;
}
int go(int index, int p_index, int[] nums) {
xors[index] = nums[index];
for (var node : map.getOrDefault(index, new ArrayList<>())) {
if (p_index != node) {
xors[index] = xors[index] ^ go(node, index, nums);
}
}
// System.out.println("xors: " + index + "\t" + xors[index]);
return xors[index];
}
}Happy Learning – If you require any further information, feel free to contact me.
![[Solved] Maximum Sum of an Hourglass LeetCode Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/10/Solved-Maximum-Sum-of-an-Hourglass-LeetCode-Contest-Problem-300x199.png)
