[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:

1. Get the XOR of all the values of the nodes for each of the three components respectively.
2. 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 are 4 ^ 5 ^ 7 = 6, 1 ^ 9 = 8, and 3 ^ 3 ^ 3 = 3. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 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.length
• 3 <= n <= 1000
• 1 <= nums[i] <= 108
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges represents 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 res

class 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.