Problem Explanation

We have a tree with n nodes, where each node has a unique genetic value. The genetic difference between two genetic values is the bitwise-XOR of their values. The tree has a root node and the parent for each node is given as an array parents. We are also given an array of queries, where each query contains a node and a value. For each query, we want to find the maximum genetic difference between the given value and any node's genetic value on the path between the query node and the root (including the query node and the root). The output should be an array of answers for each query.

Approach and Algorithm

To solve this problem, we'll use a data structure called a binary trie. A binary trie is a tree data structure where a bitwise representation of a number is stored with each bit occupying a node in the trie. It can be used to efficiently find the maximum XOR between a query number and numbers already stored in the trie.

To implement the solution, we'll use the following data structure and functions:

• TrieNode: The trie node structure with two children pointers for 0 and 1 and a count value to store how many nodes are passing through this trie node.
• Trie: The trie class with functions to insert a number with a given value and query the trie for the maximum XOR for a given number.
• dfs: A function to traverse the tree in depth-first search manner, updating the trie as it goes and calculating the answers for each query.

We'll create a tree from the given parents array and for each query, we'll associate the queries with their respective tree nodes. Then, we'll traverse the tree using the dfs function. The dfs function will take the trie, tree, nodeToQueries, and ans as arguments.

During the traversal, each node value is inserted in the trie. For each query associated with the current node, we'll calculate the answer using the trie query function and store it in the ans array. Once the traversal of the children of the current node is complete, we will remove the node from the trie.

Example

Let's walk through a simple example:

1
2
3parents = [3, 3, 0, -1]
4queries = [[0, 1], [2, 6], [2, 2], [3, 7]]

1. The tree structure from the parents array would be:

1
2
3   3
4  / \
5 0   1
6  \
7   2

2. The nodeToQueries map will look like this:

1
2
3{
4  0: [(0, 1)],
5  2: [(1, 6), (2, 2)],
6  3: [(3, 7)]
7}

3. Now, we will perform a depth-first search starting from the root (node 3).

4. First, we insert the value 3 into the trie:

1
2
3  Trie (for value 3):
4   * 1
5  / \
6null  *
7/_\ |_\

5. We process the query for node 3: 3 XOR 7 = 4

6. Now, we traverse to the left child (node 0), and insert the value 0 into the trie:

1
2
3   Trie (for values 0 and 3):
4      * 2
5   __/ \__
6  *       *
7 /_\     /_\

7. We process the query for node 0: 0 XOR 1 = 1

8. Now, we traverse to the right child (node 2), and insert the value 2 into the trie:

1
2
3  Trie (for values 0, 2, and 3):
4        * 3
5     __/    \__
6    *          *
7   / \__    __/ \
8  *     *  *     *
9 /_\   /_\/_\   /_\

9. We process the queries for node 2: 2 XOR 6 = 4 and 2 XOR 2 = 0

10. After processing all queries, the final ans array would be [1, 4, 0, 4].

C++ Solution

1
2cpp
3#include<bits/stdc++.h>
4using namespace std;
5
6struct TrieNode {
7  vector<shared_ptr<TrieNode>> children;
8  int count = 0;
9  TrieNode() : children(2) {}
10};
11
12class Trie {
13 public:
14  void update(int num, int val) {
15    shared_ptr<TrieNode> node = root;
16    for (int i = kHeight; i >= 0; --i) {
17      const int bit = (num >> i) & 1;
18      if (node->children[bit] == nullptr)
19        node->children[bit] = make_shared<TrieNode>();
20      node = node->children[bit];
21      node->count += val;
22    }
23  }
24
25  int query(int num) {
26    int ans = 0;
27    shared_ptr<TrieNode> node = root;
28    for (int i = kHeight; i >= 0; --i) {
29      const int bit = (num >> i) & 1;
30      const int targetBit = bit ^ 1;
31      if (node->children[targetBit] && node->children[targetBit]->count) {
32        ans += 1 << i;
33        node = node->children[targetBit];
34      } else {
35        node = node->children[targetBit ^ 1];
36      }
37    }
38    return ans;
39  }
40
41 private:
42  static constexpr int kHeight = 17;
43  shared_ptr<TrieNode> root = make_shared<TrieNode>();
44};
45
46class Solution {
47 public:
48  vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
49    const int n = parents.size();
50    vector<int> ans(queries.size());
51    int rootVal = -1;
52    vector<vector<int>> tree(n);
53    unordered_map<int, vector<pair<int, int>>> nodeToQueries;
54    Trie trie;
55
56    for (int i = 0; i < parents.size(); ++i)
57      if (parents[i] == -1)
58        rootVal = i;
59      else
60        tree[parents[i]].push_back(i);
61
62    for (int i = 0; i < queries.size(); ++i) {
63      const int node = queries[i][0];
64      const int val = queries[i][1];
65      nodeToQueries[node].emplace_back(i, val);
66    }
67
68    dfs(rootVal, trie, tree, nodeToQueries, ans);
69    return ans;
70  }
71
72 private:
73  void dfs(int node, Trie& trie, const vector<vector<int>>& tree,
74           const unordered_map<int, vector<pair<int, int>>>& nodeToQueries,
75           vector<int>& ans) {
76    trie.update(node, 1);
77
78    if (const auto it = nodeToQueries.find(node); it != cend(nodeToQueries))
79      for (const auto& [i, val] : it->second)
80        ans[i] = trie.query(val);
81
82    for (const int child : tree[node])
83      dfs(child, trie, tree, nodeToQueries, ans);
84
85    trie.update(node, -1);
86  }
87};
88
89int main() {
90  vector<int> parents = {3, 3, 0, -1};
91  vector<vector<int>> queries = {{0, 1}, {2, 6}, {2, 2}, {3, 7}};
92  Solution sol;
93  vector<int> results = sol.maxGeneticDifference(parents, queries);
94  for (int res : results) {
95    cout << res << " ";
96  }
97  return 0;
98}

Python Solution

1
2python
3from typing import List, Tuple
4
5class Trie:
6    
7    def __init__(self):
8        self.root = {}
9    
10    def update(self, num: int, val: int) -> None:
11        node = self.root
12        for i in range(17, -1, -1):
13            bit = (num >> i) & 1
14            if bit not in node:
15                node[bit] = {"count": 0}
16            node = node[bit]
17            node["count"] += val
18    
19    def query(self, num: int) -> int:
20        ans = 0
21        node = self.root
22        for i in range(17, -1, -1):
23            bit = (num >> i) & 1
24            target_bit = bit ^ 1
25            if target_bit in node and node[target_bit]["count"]:
26                ans += 1 << i
27                node = node[target_bit]
28            else:
29                node = node[bit]
30        return ans
31    
32class Solution:
33    
34    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
35        n = len(parents)
36        ans = [0] * len(queries)
37        root_val = -1
38        tree = [[] for _ in range(n)]
39        node_to_queries = {}
40        trie = Trie()
41
42        for i in range(n):
43            if parents[i] == -1:
44                root_val = i
45            else:
46                tree[parents[i]].append(i)
47
48        for i in range(len(queries)):
49            node, val = queries[i]
50            if node not in node_to_queries:
51                node_to_queries[node] = []
52            node_to_queries[node].append((i, val))
53
54        def dfs(node: int, trie: Trie, tree: List[List[int]], node_to_queries: dict, ans: List[int]) -> None:
55            trie.update(node, 1)
56
57            if node in node_to_queries:
58                for i, val in node_to_queries[node]:
59                    ans[i] = trie.query(val)
60
61            for child in tree[node]:
62                dfs(child, trie, tree, node_to_queries, ans)
63
64            trie.update(node, -1)
65        
66        dfs(root_val, trie, tree, node_to_queries, ans)
67        return ans
68
69# Test
70parents = [3, 3, 0, -1]
71queries = [[0, 1], [2, 6], [2, 2], [3, 7]]
72sol = Solution()
73print(sol.maxGeneticDifference(parents, queries))  # Output should be [1, 4, 0, 4]

JavaScript Solution

1
2javascript
3class Trie {
4    
5    constructor() {
6        this.root = {};
7    }
8    
9    update(num, val) {
10        let node = this.root;
11        for (let i = 17; i >= 0; --i) {
12            const bit = (num >> i) & 1;
13            if (!(bit in node)) {
14                node[bit] = { count: 0 };
15            }
16            node = node[bit];
17            node.count += val;
18        }
19    }
20    
21    query(num) {
22        let ans = 0;
23        let node = this.root;
24        for (let i = 17; i >= 0; --i) {
25            const bit = (num >> i) & 1;
26            const target_bit = bit ^ 1;
27            if (target_bit in node && node[target_bit].count) {
28                ans += 1 << i;
29                node = node[target_bit];
30            } else {
31                node = node[bit];
32            }
33        }
34        return ans;
35    }
36    
37}
38
39function maxGeneticDifference(parents, queries) {
40    const n = parents.length;
41    const ans = Array(queries.length).fill(0);
42    let root_val = -1;
43    const tree = Array.from({ length: n }, () => []);
44    const node_to_queries = {};
45    const trie = new Trie();
46    
47    for (let i = 0; i < n; ++i) {
48        if (parents[i] === -1) {
49            root_val = i;
50        } else {
51            tree[parents[i]].push(i);
52        }
53    }
54
55    for (let i = 0; i < queries.length; ++i) {
56        const [node, val] = queries[i];
57        if (!(node in node_to_queries)) {
58            node_to_queries[node] = [];
59        }
60        node_to_queries[node].push([i, val]);
61    }
62
63    function dfs(node, trie, tree, node_to_queries, ans) {
64        trie.update(node, 1);
65
66        if (node in node_to_queries) {
67            for (const [i, val] of node_to_queries[node]) {
68                ans[i] = trie.query(val);
69            }
70        }
71
72        for (const child of tree[node]) {
73            dfs(child, trie, tree, node_to_queries, ans);
74        }
75
76        trie.update(node, -1);
77    }
78    
79    dfs(root_val, trie, tree, node_to_queries, ans);
80    return ans;
81}
82
83Parents = [3, 3, 0, -1]
84queries = [[0, 1], [2, 6], [2, 2], [3, 7]]
85console.log(maxGeneticDifference(parents, queries));  // Output should be [1, 4, 0, 4]

All three solutions provided are for the problem as originally described using the appropriate Trie data structure and depth-first search traversal in C++, Python, and JavaScript.

Solution Implementation