2322. Minimum Score After Removals on a Tree
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.
Flowchart Walkthrough
Let's dissect the algorithm for LeetCode 2322. Minimum Score After Removals on a Tree using the Flowchart. Here's a detailed exploration using the flowchart:
Is it a graph?
- Yes: In this problem, the tree is essentially a graph structure where each node represents a node in the tree and each edge connects two nodes.
Is it a tree?
- Yes: The problem explicitly mentions that it involves operations on a tree.
According to the flowchart:
- Following the "Is it a tree? Yes" path, we end up directly at the node for "DFS" in the flowchart.
Conclusion:
- The flowchart suggests using Depth-First Search (DFS) for this tree-based problem. DFS can efficiently navigate the tree for required computations, especially when modifications like edge removals are involved, making it suitable for operations like subtree analysis and updating tree states.
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.
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 nodei
tox
.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 nodei
that are not equal tofa
(parent) orx
(detached node) and calculates the XOR of the subtree rooted at these children recursively.
-
dfs2(i, fa, x)
: This function is similar todfs
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 childj
ofi
, it computes the XOR valuesa
,b
, andc
for the subtrees after the second removal. - It calculates a temporary score
t
by finding the maximum and minimum ofa
,b
,c
and finding their difference. - It updates
ans
with the minimum between the currentans
and the temporary scoret
.
- It performs the same actions as
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 nodei
.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 updatesans
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
1 0 2 / \ 3 1 2 4 / \ 53 4
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
, and5
, respectively, giving a score of5 - 1 = 4
. - If we remove edges 1–3 and then 0–1, we get components with XOR values
4
,1^2 = 3
, and1^5 = 4
, respectively, giving a score of4
. - Lastly, removing edges 2–4 and then 0–2, we get components with XOR values
1^2^3 = 0
,4
, and1
, respectively, giving a score of4 - 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
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 ofO(E)
whereE
is the number of edges in the graph. - Computing the overall XOR
s
of all values innums
is done inO(N)
time, whereN
is the number of vertices in the graph. - The double
for
loop implies thatdfs
anddfs2
are calledO(N^2)
times.
For each call to dfs
and dfs2
:
- The
dfs
function performs a Depth-First Search (DFS) for each node, which takesO(N)
time. - Since
dfs2
is also a recursive DFS call, it takesO(N)
time but is called within a loop for each of the nodes, resulting inO(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
requiresO(N + E)
space. - The recursive
dfs
anddfs2
functions contribute to the space complexity by the call stack which can go as deep asO(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.
Which of the following is a good use case for backtracking?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.