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:

  1. dfs1(i, fa) - calculates and returns the sum of values for the subtree rooted at node i, excluding the edge to the parent node fa.
  2. dfs2(i, fa) - searches the trie for the value that gives the maximum XOR with the sum for the subtree rooted at node i and 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.

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

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 ans if this is greater than the current ans.
  • 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 update ans.

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.

Python Solution

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
72

Java Solution

1class 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}
101

C++ Solution

1#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};
95

Typescript Solution

1// 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}
90

Time and Space Complexity

Time Complexity

Let's analyze the time complexity of the given code based on its different parts:

  • The Trie insertion (insert) method runs with a complexity of O(W), where W is the maximum length of the binary representation of the numbers being inserted. As W is fixed at 48 (loop runs from 47 to 0), this is essentially O(1) in the context of this problem.
  • Each dfs1 call computes the sum of the subtree rooted at the current node which takes O(1) for each node itself, but due to recursion, it will be called N times, where N is the number of vertices in the graph i.e., the number of nodes in the trie. So, the complexity will be O(N).
  • Similarly, each dfs2 call will check for the maximum XOR in the subtree which again takes O(1) for processing at each node, but invoked N times overall. The search method in Trie has the same fixed O(W) complexity, which is O(1) in this context. Therefore, dfs2 has a complexity of O(N).
  • In addition to the calls of functions, the construction of the graph g takes O(E) where E is the number of edges. Since this is a tree (or an unrooted graph which can be seen as a tree with N nodes and N-1 edges), here E = 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 Trie structure uses O(N) space due to potentially storing a value for each node.
  • The dfs1 and dfs2 recursive calls will have a recursion depth of up to N, in the worst case of the tree being a straight line. This leads to a space complexity of O(N) due to the recursion stack.
  • Additional space is needed for storing the graph g, which is O(E), as well as the sums s, taking O(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)

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.


TA 👨‍🏫