2322. Minimum Score After Removals on a Tree

HardBit ManipulationTreeDepth-First SearchArray

Problem Description

In this problem, we're given an undirected connected tree consisting of n nodes. These nodes are labeled from 0 to n - 1, and there are n - 1 edges, which makes the graph a tree (since a tree always has one less edge than the number of nodes). Along with the tree structure, we are also given the value for each node in an integer array nums such that nums[i] represents the value of the i-th node.

Our task is to find the minimum score that could be achieved by removing exactly two edges from the tree, splitting it into three connected components. The score is calculated as follows:

Perform the XOR operation on the values of all the nodes in each of the three components to find three XOR values.
Find the difference between the largest and smallest of these three XOR values. This difference is the score for the particular pair of edges removed.

Our goal is to minimize this score across all possible pairs of edge removals.

Intuition

The solution exploits properties of XOR and the structure of the tree. XOR (exclusive OR) is a bitwise operation that is associative and commutative, which is useful for manipulating the values across the tree in certain orders.

Here's how we arrive at the solution:

Since the tree is connected and undirected, when two edges are removed, we are guaranteed to get three separate components. The XOR of each component can be computed iteratively or recursively.
To minimize the score, we should consider each possible pair of edges that could be removed, calculate the score for each case, and keep track of the minimum score encountered.
For each pair of edges removed, we calculate the XOR of the tree component that is detached first, and then we proceed to find the XOR of the subtrees of the remaining component after removing the second edge. This helps us in keeping track of the resulting three XOR values and the score for each pair of removed edges.
A depth-first search (DFS) algorithm is used twice: first, to calculate the initial component XOR before the second edge is removed, and second, to calculate the XOR values of the two smaller components after the second edge is removed.
By iterating through all possible pairs of edges to remove, we can calculate the XOR values and the resulting scores, and then return the smallest score encountered.

The key to this algorithm is a combination of brute-force search over all pairs of edges for removal and efficient calculation of XOR of components using DFS. Each node is visited multiple times across different DFS calls, and the calculation of the three XOR values is done in a way that leverages the removal of edges to partition the tree.

Learn more about Tree and Depth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The implementation of the solution follows the intuition closely by using a DFS approach to calculate the XOR values and iterate through all possible pairs of edges to remove. Let's examine the essential parts of the code in detail:

Data Structures

g: A defaultdict of lists used as an adjacency list representation of the tree where each key is a node and its value is the list of nodes it's connected to by an edge.
s: A variable used to hold the XOR of all the values in the tree.
ans: A variable that keeps track of the minimum score encountered during the computation.

Depth-First Search (DFS)

Two DFS functions are defined: dfs and dfs2.

dfs(i, fa, x): This function calculates the XOR value of the component resulting from removing an edge from the node i to x.
- i is the current node.
- fa is the parent node to avoid going back up the tree.
- x is the node which has been detached by edge removal so that the traversal does not cross the removed edge.
- The function traverses all children (j) of the current node i that are not equal to fa (parent) or x (detached node) and calculates the XOR of the subtree rooted at these children recursively.
dfs2(i, fa, x): This function is similar to dfs but is used after removing the first edge to proceed with the second removal. It calculates the XOR values of the remaining components and updates the minimum score (ans) accordingly.
- It performs the same actions as dfs, but in addition, for each child j of i, it computes the XOR values a, b, and c for the subtrees after the second removal.
- It calculates a temporary score t by finding the maximum and minimum of a, b, c and finding their difference.
- It updates ans with the minimum between the current ans and the temporary score t.

Iteration Through Edge Pairs

The main part of the algorithm iterates through all nodes i and their neighbors j to simulate the removal of the edge between i and j and compute the corresponding scores.

for i in range(n): Iterates over all nodes.
for j in g[i]: Iterates over all neighbors of node i.
s1 = dfs(i, -1, j): Calculates the XOR value of the component cut off by the first removal.
dfs2(i, -1, j): Calculates the XOR values of the smaller components remaining for all possible second removals and updates ans.

Return Value

return ans: Finally, it returns the minimum score encountered during the iteration, which is the desired solution to the problem.

By combining these algorithms and patterns, the given solution code systematically explores all possible edge removals and computes the XOR-based score efficiently, honoring the properties of the tree and the XOR operation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Example Walkthrough

Let's illustrate the solution approach using a small example with a tree of 5 nodes where the node values are given by nums = [1, 2, 3, 4, 5]. We structure the tree as follows, with g being the adjacency list representation:

With g as:

1g = {0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]}

The very first step would be to find the XOR of all the values in the tree, which we store in the variable s. This gives us s = 1^2^3^4^5, which simplifies to s = 1.

Now, we walk through each possible pair of edge removals and calculate the score for each case. Let's start by considering the removal of the edge between nodes 0 and 1 (first removal).

When we remove the edge between 0 and 1, dfs(0, -1, 1) is called to compute the XOR for the cut-off component. At this stage, the component consists of only node 1 with the value 2. Now s1 is equal to 2.

For the second removal, we iterate over all neighbors of node 0 which are not 1 (i.e., node 2). This is where we call dfs2(0, -1, 2) which computes the XOR for the other components by removing the edge between node 0 and node 2. This leads us to have the component 0 with XOR value 1, component 2-4 with XOR value 2^5 = 7, and as previously found the component 1-3 with XOR value 2^4 = 6. The difference between the maximum and minimum XOR values is 7 - 1 = 6.

Next, we continue with all possible pairs:

Removing edges 0–2 and then 2–4, we get components with XOR values 1^2^3^4 = 4, 1, and 5, respectively, giving a score of 5 - 1 = 4.
If we remove edges 1–3 and then 0–1, we get components with XOR values 4, 1^2 = 3, and 1^5 = 4, respectively, giving a score of 4.
Lastly, removing edges 2–4 and then 0–2, we get components with XOR values 1^2^3 = 0, 4, and 1, respectively, giving a score of 4 - 0 = 4.

The scores we encountered were 6, 4, 4, 4. Therefore, ans will be the minimum score from these calculations, which in this case is 4.

Finally, the algorithm returns ans, which is the minimum score, 4 in our example. This approach systematically checks each possible pair of edge removals to find the pair that results in the minimum XOR difference score, as per the given problem statement.

Solution Implementation

1from collections import defaultdict
2from math import inf
3
4class Solution:
5    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
6        # Perform DFS to calculate xor of the subtree rooted at node `i`
7        # excluding any visited node `fa` and the edge broken at node `x`
8        def dfs(node, parent, exclude_node):
9            result = nums[node]
10            for neighbor in graph[node]:
11                if neighbor != parent and neighbor != exclude_node:
12                    result ^= dfs(neighbor, node, exclude_node)
13            return result
14
15        # Another DFS to calculate the minimum score after breaking the edge
16        # at node `x` by considering different divisions of the tree and
17        # updating the answer with the possible score
18        def dfs_with_score(node, parent, exclude_node):
19            nonlocal total, subtree_xor, min_score
20            result = nums[node]
21            for neighbor in graph[node]:
22                if neighbor != parent and neighbor != exclude_node:
23                    subtree_result = dfs_with_score(neighbor, node, exclude_node)
24                    result ^= subtree_result
25                    remaining_xor = subtree_xor ^ subtree_result
26                    rest_of_tree_xor = total ^ subtree_xor
27                    max_xor = max(subtree_result, remaining_xor, rest_of_tree_xor)
28                    min_xor = min(subtree_result, remaining_xor, rest_of_tree_xor)
29                    score_difference = max_xor - min_xor
30                    min_score = min(min_score, score_difference)
31            return result
32
33        # Create a graph from the edges
34        graph = defaultdict(list)
35        for start_node, end_node in edges:
36            graph[start_node].append(end_node)
37            graph[end_node].append(start_node)
38
39        # Calculate the total xor of all values
40        total = 0
41        for value in nums:
42            total ^= value
43
44        # Initialize minimum score to infinity
45        min_score = inf
46
47        # Iterate over all nodes in the graph
48        for i in range(len(nums)):
49            # Iterate over its connected edges to break one at a time
50            for j in graph[i]:
51                # Perform dfs to get xor of subtree after breaking edge between i and j
52                subtree_xor = dfs(i, -1, j)
53                # Perform dfs to get the minimum score after breaking edge between i and j
54                dfs_with_score(i, -1, j)
55              
56        # Return the minimum score found
57        return min_score
58

1class Solution {
2    private int totalXor;               // Holds the xor of all elements in nums
3    private int subtreeXor;             // Xor value of a subtree
4    private int nodeCount;              // Holds the number of nodes in the graph/tree
5    private int minimumScore = Integer.MAX_VALUE; // The minimum score we intend to find
6    private int[] nodeValues;           // Holds the values at the nodes
7    private List<Integer>[] graph;      // The graph represented as an adjacency list
8
9    public int minimumScore(int[] nums, int[][] edges) {
10        nodeCount = nums.length;
11        graph = new List[nodeCount];
12        nodeValues = nums;
13        // Initialize lists for all graph nodes
14        Arrays.setAll(graph, k -> new ArrayList<>());
15        // Construct the graph from the edge list
16        for (int[] edge : edges) {
17            int from = edge[0], to = edge[1];
18            graph[from].add(to);
19            graph[to].add(from);
20        }
21        // Compute the xor of all values in nums
22        for (int value : nums) {
23            totalXor ^= value;
24        }
25        // Try cutting from each edge and calculate minimum score
26        for (int i = 0; i < nodeCount; ++i) {
27            for (int adjacentNode : graph[i]) {
28                // Perform the first DFS to find the xor of a subtree
29                subtreeXor = firstDfs(i, -1, adjacentNode);
30                // Perform the second DFS to determine the minimum score possible
31                secondDfs(i, -1, adjacentNode);
32            }
33        }
34        return minimumScore;
35    }
36
37    private int firstDfs(int node, int parent, int excludedNode) {
38        int result = nodeValues[node];
39        // Traverse the children (excluding the parent and the excluded node)
40        for (int child : graph[node]) {
41            if (child != parent && child != excludedNode) {
42                result ^= firstDfs(child, node, excludedNode);
43            }
44        }
45        return result;
46    }
47
48    private int secondDfs(int node, int parent, int excludedNode) {
49        int result = nodeValues[node];
50        // Traverse the children (excluding the parent and the excluded node)
51        for (int child : graph[node]) {
52            if (child != parent && child != excludedNode) {
53                // Calculate xor for this subtree
54                int subtreeResult = secondDfs(child, node, excludedNode);
55                result ^= subtreeResult;
56                // Partition the graph into 3 parts and find the score
57                int firstPart = subtreeResult;
58                int secondPart = subtreeXor ^ firstPart;
59                int thirdPart = totalXor ^ subtreeXor;
60                // Calculate the temporary score
61                int score = Math.max(Math.max(firstPart, secondPart), thirdPart) 
62                          - Math.min(Math.min(firstPart, secondPart), thirdPart);
63                // Update the minimum score if we found a better one
64                minimumScore = Math.min(minimumScore, score);
65            }
66        }
67        return result;
68    }
69}
70

1#include <vector>
2#include <climits>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> values;  // Values corresponding to each node
9    int totalXor;        // XOR of all values
10    int subtreeXor;      // XOR of the values in a subtree
11    int nodeCount;       // Number of nodes in the graph
12    int minDifference = INT_MAX; // Minimum absolute difference between the XOR of three parts
13    vector<vector<int>> graph; // Adjacency list representation of the graph
14
15    // Main function that solves the problem by iterating over each edge 
16    // and considering it as a potential cut to form two trees
17    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
18        nodeCount = nums.size();
19        graph.resize(nodeCount, vector<int>());
20
21        // Construct the graph
22        for (auto& e : edges) {
23            int from = e[0], to = e[1];
24            graph[from].push_back(to);
25            graph[to].push_back(from);
26        }
27
28        // Calculate the totalXor for all the values
29        totalXor = 0;
30        for (int& v : nums) totalXor ^= v;
31
32        // Store the given values
33        values = nums;
34
35        // Iterate over all nodes and their connected nodes
36        for (int i = 0; i < nodeCount; ++i) {
37            for (int neighbor : graph[i]) {
38                // Find the XOR for one subtree
39                subtreeXor = dfs(i, -1, neighbor);
40                // Attempt to find the minimum difference by cutting another edge in the formed subtree
41                dfs2(i, -1, neighbor);
42            }
43        }
44        return minDifference;
45    }
46
47    // DFS to find the XOR of all values under the current node, ignoring the parent and the excluded node x
48    int dfs(int current, int parent, int excludedNode) {
49        int currentXor = values[current];
50        for (int next : graph[current])
51            if (next != parent && next != excludedNode) 
52                currentXor ^= dfs(next, current, excludedNode);
53        return currentXor;
54    }
55
56    // Second DFS to try out different cuts in the subtree rooted at 'current' and calculate the resulting minimum difference
57    int dfs2(int current, int parent, int excludedNode) {
58        int currentXor = values[current];
59        for (int next : graph[current])
60            if (next != parent && next != excludedNode) {
61                int a = dfs2(next, current, excludedNode);
62                currentXor ^= a;
63                int b = subtreeXor ^ a;
64                int c = totalXor ^ subtreeXor;
65                int maxPart = max(max(a, b), c);
66                int minPart = min(min(a, b), c);
67                int difference = maxPart - minPart;
68                minDifference = min(minDifference, difference);
69            }
70        return currentXor;
71    }
72};
73

1let values: number[];  // Values corresponding to each node
2let totalXor: number;  // XOR of all values
3let subtreeXor: number;  // XOR of the values in a subtree
4let nodeCount: number;  // Number of nodes in the graph
5let minDifference: number = Number.MAX_SAFE_INTEGER; // Minimum absolute difference between the XOR of three parts
6let graph: number[][]; // Adjacency list representation of the graph
7
8// Main function that solves the problem by iterating over each edge 
9// and considering it as a potential cut to form two trees
10function minimumScore(nums: number[], edges: number[][]): number {
11    nodeCount = nums.length;
12    graph = new Array(nodeCount).fill(0).map(() => []);
13
14    // Construct the graph
15    edges.forEach(e => {
16        const [from, to] = e;
17        graph[from].push(to);
18        graph[to].push(from);
19    });
20
21    // Calculate the totalXor for all the values
22    totalXor = nums.reduce((xor, num) => xor ^ num, 0);
23
24    // Store the given values
25    values = nums.slice();
26
27    // Iterate over all nodes and their connected nodes
28    for (let i = 0; i < nodeCount; ++i) {
29        graph[i].forEach(neighbor => {
30            // Find the XOR for one subtree
31            subtreeXor = dfs(i, -1, neighbor);
32            // Attempt to find the minimum difference by cutting another edge in the formed subtree
33            dfs2(i, -1, neighbor);
34        });
35    }
36
37    return minDifference;
38}
39
40// DFS to find the XOR of all values under the current node, ignoring the parent and the excluded node
41function dfs(current: number, parent: number, excludedNode: number): number {
42    let currentXor: number = values[current];
43    graph[current].forEach(next => {
44        if (next !== parent && next !== excludedNode)
45            currentXor ^= dfs(next, current, excludedNode);
46    });
47    return currentXor;
48}
49
50// Second DFS to try out different cuts in the subtree rooted at 'current' and calculate the resulting minimum difference
51function dfs2(current: number, parent: number, excludedNode: number): number {
52    let currentXor: number = values[current];
53    graph[current].forEach(next => {
54        if (next !== parent && next !== excludedNode) {
55            let a = dfs2(next, current, excludedNode);
56            currentXor ^= a;
57            let b = subtreeXor ^ a;
58            let c = totalXor ^ subtreeXor;
59            let maxPart = Math.max(a, b, c);
60            let minPart = Math.min(a, b, c);
61            let difference = maxPart - minPart;
62            minDifference = Math.min(minDifference, difference);
63        }
64    });
65    return currentXor;
66}
67

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the algorithm can be broken down into the main operations:

Building the adjacency list g has a time complexity of O(E) where E is the number of edges in the graph.
Computing the overall XOR s of all values in nums is done in O(N) time, where N is the number of vertices in the graph.
The double for loop implies that dfs and dfs2 are called O(N^2) times.

For each call to dfs and dfs2:

The dfs function performs a Depth-First Search (DFS) for each node, which takes O(N) time.
Since dfs2 is also a recursive DFS call, it takes O(N) time but is called within a loop for each of the nodes, resulting in O(N^2) time in the worst case.

Considering the above, the overall time complexity is dominated by the O(N^2) calls to dfs and dfs2. Therefore, the final time complexity is O(N^2 * N) which simplifies to O(N^3).

Space Complexity

The space complexity can be broken down as follows:

The adjacency list g requires O(N + E) space.
The recursive dfs and dfs2 functions contribute to the space complexity by the call stack which can go as deep as O(N) in the case of a skewed tree or one with one path.

Therefore, the space complexity of the algorithm is O(N + E) for the adjacency list and O(N) for the recursive call stack, making the final space complexity dominated by O(N + E). However, in a connected graph, E is at least O(N), so this simplifies to O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2322. Minimum Score After Removals on a Tree

Problem Description

Intuition

Solution Approach

Data Structures

Depth-First Search (DFS)

Iteration Through Edge Pairs

Return Value

Example Walkthrough

Solution Implementation

Time and Space Complexity