2479. Maximum XOR of Two Non-Overlapping Subtrees
Problem Description
The problem is based on an undirected tree consisting of n nodes labeled from 0 to n - 1. Each node in this tree has a value associated with it. We're given n as the number of nodes, an array edges that represents the edges in the tree, and an array values where each element represents the value of the corresponding node.
The goal is to select two non-overlapping subtrees (subtrees that don't share any node) and calculate the score as the bitwise XOR of the sums of the values in each subtree. The task is to find the maximum possible score we can obtain out of all possible pairs of such subtrees. If it's impossible to find such non-overlapping subtrees, the score will be 0.
Subtree is defined as a tree that includes a node and all its descendants. Non-overlapping subtrees are those that have distinct nodes and thus don't intersect at any point.
Intuition
To solve this problem, we start by understanding that we can represent each subtree by the sum of its node values. This representation helps us focus on sum values rather than the structure of the subtrees. Then, we can look for pairs of sums that produce the highest XOR.
The maximum value for the sum of the values in any subtree will be determined by the range of numbers possible in values array. Each integer can be represented by a fixed number of bits (determined by the maximum possible sum), and XOR operations are based on these bits.
Our approach makes use of a binary trie (prefix tree) which is a data structure that stores binary representations of numbers. As we traverse the tree (using Depth-First Search, or DFS), we record sums at each node and insert their binary representation into the trie. We start our search from the first node labeled 0 (the root), and each time we reach a node, we look in the trie for the complement sum that would give us the highest XOR with the current sum. We use another DFS pass for this step.
It should be noted that before inserting the sum of a subtree into the trie, we check the maximum XOR possible with the sums already in the trie, keeping track of the maximum value found.
The two DFS functions serve two purposes:
dfs1(i, fa)- calculates and returns the sum of values for the subtree rooted at nodei, excluding the edge to the parent nodefa.dfs2(i, fa)- searches the trie for the value that gives the maximum XOR with the sum for the subtree rooted at nodeiand then inserts the sum for this subtree into the trie.
By traversing the tree and maintaining these values, we can calculate the required score following the constraints given.
Learn more about Tree, Depth-First Search, Graph and Trie patterns.
Which of these pictures shows the visit order of a depth-first search?
Solution Approach
The solution provided uses two main algorithms: Depth-First Search (DFS) and a binary trie (prefix tree) for efficient computation of the maximum XOR.
DFS for Subtree Sums
The algorithm starts by constructing the adjacency list g which represents the undirected tree. The primary goal is to find subtree sums (i.e., sums of values of all nodes in a subtree) for every possible subtree rooted at every node. The dfs1 function takes care of this by recursively calculating these sums and storing them in an array s.
Starting from the root node 0, we call dfs1(0, -1). It traverses the tree and computes the sum for each subtree. This process continues recursively until all nodes are visited, and along the way, each node's subtree sum gets updated, accounting for the sum of its children's subtree sums plus its own value.
Binary Trie
Next, we utilize a Trie data structure that stores binary representations of the numbers encountered during the DFS traversal. Each node in the Trie can have up to two children, corresponding to the 0 or 1 bit values at each level of binary representation. This Trie helps to efficiently search for the binary number that, when XORed with a given binary number, yields the highest value.
To insert numbers into the Trie, we use the insert method of the Trie class. To find the maximum XOR, we use the search method which operates on the principle that for each bit in a number, the bit that would give the highest XOR is 1 if the current bit is 0, and 0 if the current bit is 1.
Maximizing the XOR
The heart of the solution lies in the function dfs2. It performs another DFS traversal of the tree. At each node, before inserting the subtree sum into the trie, it searches for the maximum XOR achievable with the sums already existing in the Trie. This search is done by the call tree.search(s[i]). It sets the highest XOR found in a global variable ans.
Once the search is completed for the current node's subtree sum, this sum is then inserted into the Trie using [tree](/problems/tree_intro).insert(s[i]) to update possible XOR pairs for the subsequent nodes.
The main class Solution has a function maxXor, which initializes the adjacency list, subtree sum array, and the Trie. It then carries out the two DFS operations described above โ first to compute the subtree sums and second to find the maximum XOR by searching and inserting in the Trie.
The resultant maximum XOR value stored in ans is finally returned, representing the highest score that can be achieved under the problem constraints.
Which data structure is used to implement recursion?
Example Walkthrough
Let's walk through a simplified example to illustrate the solution approach.
Example:
Given n = 4, edges = [[0, 1], [1, 2], [1, 3]], and values = [3, 6, 1, 5].
The undirected tree looks like this:
1 0 2 | 3 1 4 / \ 5 2 3
The values are associated as follows: node 0 -> 3, node 1 -> 6, node 2 -> 1, and node 3 -> 5.
Step 1: Perform DFS to Calculate Subtree Sums (dfs1)
Starting with node 0, we perform DFS to calculate subtree sums.
For node 0:
- It only has 1 child node (1), so we visit node 1.
For node 1:
- It has two children nodes (2, 3). We visit each child node and calculate their sums.
- For node 2,
subtree_sum = value[2] = 1. - For node 3,
subtree_sum = value[3] = 5.
The sum of the subtree rooted at node 1 will be its own value plus the sum of its children (6 + 1 + 5 = 12). Therefore, subtree_sum[1] = 12.
Back to node 0, the subtree sum including node 0 will be value[0] + subtree_sum[1] = 3 + 12 = 15.
Step 2: Constructing the Binary Trie
We initialize our Trie data structure. We will insert binary representations of these subtree sums into the Trie later in dfs2.
Step 3: Perform DFS to Maximize XOR and Insert into Binary Trie (dfs2)
Starting again with node 0, we do the following:
- Node 0's subtree sum is 15. We search in the Trie for the highest XOR (it's empty initially, so this step is skipped), and insert the binary representation of 15.
- Moving to node 1, its sum is 12. We search for the XOR pair in the Trie (15). The maximum XOR result is 15 XOR 12 = 3. We update the
ansif this is greater than the currentans. - Continuing to nodes 2 and 3, each value's XOR with 15 is calculated: (15 XOR 1 = 14), and (15 XOR 5 = 10). If any of these is higher than the current
ans, we updateans.
Conclusion:
Our binary trie has entries for sums 15 (node 0 sub-tree), 12 (node 1 sub-tree), and individual values 1 and 5 for nodes 2 and 3. The maximum XOR value so far is 14 (from 1 XOR 15). Therefore, ans = 14 represents the highest possible score that can be achieved.
Note that during the dfs2 traversal, we ensure not to XOR sums of overlapping subtrees since we never consider the sum of a node and its direct ancestor.
Solution Implementation
1from collections import defaultdict
2
3class Trie:
4 def __init__(self):
5 # Each Trie node has an array of two children for binary representation
6 self.children = [None] * 2
7
8 def insert(self, num):
9 # Insert a number into the Trie
10 node = self
11 # We start from the 47th bit since we're assuming 48-bit integers
12 for i in range(47, -1, -1):
13 bit = (num >> i) & 1
14 if node.children[bit] is None:
15 node.children[bit] = Trie()
16 node = node.children[bit]
17
18 def search(self, num):
19 # Search for the number in the Trie that, when XORed with 'num',
20 # gives the maximum value
21 node = self
22 max_xor_val = 0
23 for i in range(47, -1, -1):
24 bit = (num >> i) & 1
25 if node is None:
26 return max_xor_val
27 if node.children[bit ^ 1]:
28 max_xor_val = (max_xor_val << 1) | 1
29 node = node.children[bit ^ 1]
30 else:
31 max_xor_val <<= 1
32 node = node.children[bit]
33 return max_xor_val
34
35
36class Solution:
37 def maxXor(self, n: int, edges: list, values: list) -> int:
38
39 def dfs_collect_sum(node, parent):
40 # Collect sum of the values using depth-first search
41 total_sum = values[node]
42 for neighbor in graph[node]:
43 if neighbor != parent:
44 total_sum += dfs_collect_sum(neighbor, node)
45 subtree_sum[node] = total_sum
46 return total_sum
47
48 def dfs_find_max(node, parent):
49 # Find the maximum XOR value using depth-first search
50 nonlocal max_xor
51 max_xor = max(max_xor, trie.search(subtree_sum[node]))
52 for neighbor in graph[node]:
53 if neighbor != parent:
54 dfs_find_max(neighbor, node)
55 trie.insert(subtree_sum[node])
56
57 # Create a graph from the edges
58 graph = defaultdict(list)
59 for a, b in edges:
60 graph[a].append(b)
61 graph[b].append(a)
62
63 # Initialize the variables used to store the subtree sums and maximum XOR result
64 subtree_sum = [0] * n
65 dfs_collect_sum(0, -1) # Collect sums starting from the first node
66
67 max_xor = 0 # Initialize the maximum XOR result
68 trie = Trie() # Initialize an empty trie
69 dfs_find_max(0, -1) # Start DFS to find max XOR
70
71 return max_xor
721class Trie {
2 // Trie nodes for binary representation of numbers
3 Trie[] children = new Trie[2];
4
5 // Method to insert a number into the trie
6 void insert(long number) {
7 Trie node = this;
8 // Start from the most significant bit and iterate to the least significant bit
9 for (int i = 47; i >= 0; --i) {
10 // Extract the current bit of the number
11 int bit = (int) (number >> i) & 1;
12 // Create a new Trie node if the path doesn't exist
13 if (node.children[bit] == null) {
14 node.children[bit] = new Trie();
15 }
16 // Move to the corresponding child node
17 node = node.children[bit];
18 }
19 }
20
21 // Method to find the maximum XOR of a number with all numbers already in the trie
22 long search(long number) {
23 Trie node = this;
24 long result = 0;
25 // Start from the most significant bit and iterate to the least significant bit
26 for (int i = 47; i >= 0; --i) {
27 // Extract the current bit of the number
28 int bit = (int) (number >> i) & 1;
29 if (node == null) {
30 return result;
31 }
32 // Attempt to find the opposite bit for maximum XOR
33 if (node.children[bit ^ 1] != null) {
34 result = result << 1 | 1;
35 node = node.children[bit ^ 1];
36 } else {
37 result <<= 1;
38 node = node.children[bit];
39 }
40 }
41 return result;
42 }
43}
44
45class Solution {
46 // Graph representation using adjacency list
47 private List<Integer>[] graph;
48 // Array to store values associated with each node
49 private int[] values;
50 // Array to store the running XOR sum from the root to each node
51 private long[] xorSum;
52 // Trie to store all the XOR paths
53 private Trie trie;
54 // Variable to store the maximum XOR value found
55 private long maxXor;
56
57 // Main function to calculate the maximum XOR in the tree
58 public long maxXor(int n, int[][] edges, int[] values) {
59 graph = new List[n];
60 xorSum = new long[n];
61 this.values = values;
62 // Initialize adjacency list for each node
63 Arrays.setAll(graph, k -> new ArrayList<>());
64 // Build the graph from the edge list
65 for (var edge : edges) {
66 int from = edge[0], to = edge[1];
67 graph[from].add(to);
68 graph[to].add(from);
69 }
70 // Compute XOR sum for each node from root
71 dfs1(0, -1);
72 trie = new Trie();
73 // Find maximum XOR and insert xorSum into trie
74 dfs2(0, -1);
75 return maxXor;
76 }
77
78 // Recursive DFS to record the XOR sum from the root to each node
79 private long dfs1(int node, int parent) {
80 long sum = values[node];
81 for (int adjacent : graph[node]) {
82 if (adjacent != parent) {
83 sum += dfs1(adjacent, node);
84 }
85 }
86 xorSum[node] = sum;
87 return sum;
88 }
89
90 // Recursive DFS to find the maximum XOR and insert the XOR sums into the trie
91 private void dfs2(int node, int parent) {
92 maxXor = Math.max(maxXor, trie.search(xorSum[node]));
93 for (int adjacent : graph[node]) {
94 if (adjacent != parent) {
95 dfs2(adjacent, node);
96 }
97 }
98 trie.insert(xorSum[node]);
99 }
100}
1011#include <vector>
2#include <functional>
3
4using ll = long long; // Alias for long long data type for convenience.
5using namespace std;
6
7// A class that represents a Trie data structure for storing binary representations of numbers.
8class Trie {
9public:
10 vector<Trie*> children; // Each node has 2 children: one for bit 0, and another for bit 1.
11
12 // Constructor that initializes the children to null.
13 Trie() : children(2) {}
14
15 // Inserts a 48-bit number into the trie.
16 void insert(ll number) {
17 Trie* node = this;
18 for (int i = 47; i >= 0; --i) {
19 int bit = (number >> i) & 1; // Extract the bit at position i.
20 if (!node->children[bit])
21 node->children[bit] = new Trie(); // Create a new node if necessary.
22 node = node->children[bit]; // Move to the next node.
23 }
24 }
25
26 // Searches for the complement of x in the trie to maximize XOR.
27 ll search(ll number) {
28 Trie* node = this;
29 ll result = 0;
30 for (int i = 47; i >= 0; --i) {
31 if (!node) return result;
32 int bit = (number >> i) & 1;
33 // If the complementary bit exists, use it to maximize XOR.
34 if (node->children[bit ^ 1]) {
35 result = (result << 1) | 1;
36 node = node->children[bit ^ 1];
37 } else { // Otherwise, continue with the same bit.
38 result <<= 1;
39 node = node->children[bit];
40 }
41 }
42 return result;
43 }
44};
45
46class Solution {
47public:
48 // Returns the maximum XOR obtained by the sum of values from the root to any node.
49 long long maxXor(int n, vector<vector<int>>& edges, vector<int>& values) {
50 vector<vector<int>> graph(n); // Representation of the graph.
51 // Constructing the undirected graph from edges.
52 for (auto& edge : edges) {
53 int from = edge[0], to = edge[1];
54 graph[from].emplace_back(to);
55 graph[to].emplace_back(from);
56 }
57
58 vector<ll> prefixSum(n); // Stores the prefix sum of values from root to the node.
59
60 // Helper function to calculate prefix sum using DFS.
61 function<ll(int, int)> dfsPrefixSum = [&](int node, int parent) -> ll {
62 ll total = values[node];
63 for (int neighbor : graph[node]) {
64 if (neighbor != parent) {
65 total += dfsPrefixSum(neighbor, node);
66 }
67 }
68 prefixSum[node] = total;
69 return total;
70 };
71
72 // Initial call to calculate prefix sums.
73 dfsPrefixSum(0, -1);
74
75 Trie trie; // Trie to store the prefix sums.
76 ll result = 0;
77
78 // Helper function to find the maximum XOR and update the trie using DFS.
79 function<void(int, int)> dfsMaxXor = [&](int node, int parent) {
80 result = std::max(result, trie.search(prefixSum[node])); // Update the result.
81 for (int neighbor : graph[node]) {
82 if (neighbor != parent) {
83 dfsMaxXor(neighbor, node); // Explore neighbors.
84 }
85 }
86 trie.insert(prefixSum[node]); // Insert prefix sum into trie.
87 };
88
89 // Initial call to find maximum XOR.
90 dfsMaxXor(0, -1);
91
92 return result;
93 }
94};
951// Trie node structure for binary numbers
2class TrieNode {
3 children: TrieNode[];
4
5 constructor() {
6 this.children = []; // Initialize children to be empty
7 }
8}
9
10// Inserts a 48-bit number into the trie
11function insert(number: bigint, root:TrieNode): void {
12 let node = root;
13 for (let i = 47; i >= 0; --i) {
14 const bit = (number >> BigInt(i)) & BigInt(1); // Extract the bit at position i
15 if (!node.children[Number(bit)]) {
16 node.children[Number(bit)] = new TrieNode(); // Create a new node if necessary
17 }
18 node = node.children[Number(bit)]; // Move to the next node
19 }
20}
21
22// Searches for the complement of x in the trie to maximize XOR
23function search(number: bigint, root: TrieNode): bigint {
24 let node = root;
25 let result = BigInt(0);
26 for (let i = 47; i >= 0; --i) {
27 if (!node) return result;
28 const bit = (number >> BigInt(i)) & BigInt(1);
29 if (node.children[Number(bit ^ BigInt(1))]) {
30 result = (result << BigInt(1)) | BigInt(1);
31 node = node.children[Number(bit ^ BigInt(1))];
32 } else {
33 result <<= BigInt(1);
34 node = node.children[Number(bit)];
35 }
36 }
37 return result;
38}
39
40// Calculates the prefix sum of values from the root to the node using DFS
41function calculatePrefixSum(node: number, parent: number, graph: number[][], values: number[], prefixSum: bigint[]): bigint {
42 let total = BigInt(values[node]);
43 for (const neighbor of graph[node]) {
44 if (neighbor !== parent) {
45 total += calculatePrefixSum(neighbor, node, graph, values, prefixSum);
46 }
47 }
48 prefixSum[node] = total;
49 return total;
50}
51
52// Finds the maximum XOR value by exploring all paths and updates the trie
53function dfsMaxXor(node: number, parent: number, graph: number[][], values: number[], prefixSum: bigint[], result: bigint, root: TrieNode): bigint {
54 result = max(result, search(prefixSum[node], root)); // Update the result with the maximum XOR found
55 for (const neighbor of graph[node]) {
56 if (neighbor !== parent) {
57 dfsMaxXor(neighbor, node, graph, values, prefixSum, result, root); // Explore neighbors
58 }
59 }
60 insert(prefixSum[node], root); // Insert the current prefix sum into the trie
61 return result;
62}
63
64function maxXor(n: number, edges: number[][], values: number[]): bigint {
65 const graph: number[][] = Array.from({length: n}, () => []); // Representation of the graph
66 // Constructing the undirected graph from edges
67 for (const [from, to] of edges) {
68 graph[from].push(to);
69 graph[to].push(from);
70 }
71
72 const prefixSum: bigint[] = new Array(n); // Stores the prefix sum of values from root to the node
73
74 // Initial call to calculate prefix sums
75 calculatePrefixSum(0, -1, graph, values, prefixSum);
76
77 const root = new TrieNode(); // Trie to store the binary representations of the prefix sums
78 let result = BigInt(0);
79
80 // Initial call to find the maximum XOR
81 result = dfsMaxXor(0, -1, graph, values, prefixSum, result, root);
82
83 return result;
84}
85
86// Utility function to find the maximum of two BigIntegers
87function max(a: bigint, b: bigint): bigint {
88 return a > b ? a : b;
89}
90What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Time and Space Complexity
Time Complexity
Let's analyze the time complexity of the given code based on its different parts:
- The
Trieinsertion (insert) method runs with a complexity ofO(W), whereWis the maximum length of the binary representation of the numbers being inserted. AsWis fixed at 48 (loop runs from 47 to 0), this is essentiallyO(1)in the context of this problem. - Each
dfs1call computes the sum of the subtree rooted at the current node which takesO(1)for each node itself, but due to recursion, it will be calledNtimes, whereNis the number of vertices in the graph i.e., the number of nodes in the trie. So, the complexity will beO(N). - Similarly, each
dfs2call will check for the maximum XOR in the subtree which again takesO(1)for processing at each node, but invokedNtimes overall. Thesearchmethod inTriehas the same fixedO(W)complexity, which isO(1)in this context. Therefore,dfs2has a complexity ofO(N). - In addition to the calls of functions, the construction of the graph
gtakesO(E)whereEis the number of edges. Since this is a tree (or an unrooted graph which can be seen as a tree withNnodes andN-1edges), hereE = N - 1.
Therefore, combining these complexities, the overall time complexity is O(N) + O(E) + O(N*W) + O(N*W), which simplifies to O(N) as E = N - 1 and W is constant.
Space Complexity
Now let's look at the space complexity:
- The
Triestructure usesO(N)space due to potentially storing a value for each node. - The
dfs1anddfs2recursive calls will have a recursion depth of up toN, in the worst case of the tree being a straight line. This leads to a space complexity ofO(N)due to the recursion stack. - Additional space is needed for storing the graph
g, which isO(E), as well as the sumss, takingO(N)space.
Thus, the overall space complexity can be seen to be dominated by O(N) due to the trie, recursion stack, and arrays used.
In summary:
- Time Complexity:
O(N) - Space Complexity:
O(N)
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
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
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.