# Maximum Genetic Difference Query
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-genetic-difference-query)
Canonical: https://scaleengineer.com/dsa/problems/maximum-genetic-difference-query
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table, Trie
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
There is a rooted tree consisting of `n` nodes numbered `0` to `n - 1`. Each node's number denotes its **unique genetic value** (i.e. the genetic value of node `x` is `x`). The **genetic difference** between two genetic values is defined as the **bitwise-** **XOR** of their values. You are given the integer array `parents`, where `parents[i]` is the parent for node `i`. If node `x` is the **root** of the tree, then `parents[x] == -1`.

You are also given the array `queries` where `queries[i] = [nodei, vali]`. For each query `i`, find the **maximum genetic difference** between `vali` and `pi`, where `pi` is the genetic value of any node that is on the path between `nodei` and the root (including `nodei` and the root). More formally, you want to maximize `vali XOR pi`.

Return _an array_ `ans` _where_ `ans[i]` _is the answer to the_ `ith` _query_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-genetic-difference-query/image0.png) 

**Input:** parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
**Output:** [2,3,7]
**Explanation:** The queries are processed as follows:
- [0,2]: The node with the maximum genetic difference is 0, with a difference of 2 XOR 0 = 2.
- [3,2]: The node with the maximum genetic difference is 1, with a difference of 2 XOR 1 = 3.
- [2,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-genetic-difference-query/image1.png) 

**Input:** parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
**Output:** [6,14,7]
**Explanation:** The queries are processed as follows:
- [4,6]: The node with the maximum genetic difference is 0, with a difference of 6 XOR 0 = 6.
- [1,15]: The node with the maximum genetic difference is 1, with a difference of 15 XOR 1 = 14.
- [0,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

**Constraints:**

* `2 <= parents.length <= 105`
* `0 <= parents[i] <= parents.length - 1` for every node `i` that is **not** the root.
* `parents[root] == -1`
* `1 <= queries.length <= 3 * 104`
* `0 <= nodei <= parents.length - 1`
* `0 <= vali <= 2 * 105`

# Approaches
## Brute Force per Query
This approach directly simulates the process described in the problem. For each query, it traverses the tree from the given node up to the root, finds all ancestor nodes, and calculates the XOR value with the query's `val`, keeping track of the maximum.
**Time:** O(Q * N)

Let `Q` be the number of queries and `N` be the number of nodes. For each query, we may traverse from a leaf to the root. In the worst-case scenario of a skewed tree (like a linked list), the path length is `O(N)`. Therefore, the total time complexity is `O(Q * N)`. · **Space:** O(Q) or O(1)

The space complexity is `O(Q)` to store the answer array. If the output array is not considered part of the space complexity, the auxiliary space used is `O(1)`.
**Pros:** Simple to understand and implement.; Requires minimal extra space, making it memory efficient.
**Cons:** Extremely inefficient for large inputs, particularly for deep or skewed trees.; The time complexity of `O(Q * N)` makes it likely to fail on platforms with strict time limits (Time Limit Exceeded).
### Explanation
The brute-force method is the most straightforward way to solve the problem. It follows the problem statement literally by processing each query independently.

For each query `[node, val]`, we need to find the maximum genetic difference with any ancestor of `node`. The ancestors can be found by repeatedly following the `parents` array starting from `node` until we reach the root (where `parent == -1`).

We can implement this with a nested loop structure. The outer loop iterates through each query, and the inner loop traverses the path from the query's node to the root. During this traversal, we compute the XOR of `val` with each node's genetic value (which is its index) and maintain the maximum XOR value found so far.

Here is a Java code snippet illustrating this approach:
```java
class Solution {
    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.length;
        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            
            int max_xor = -1;
            int curr_node = node;
            
            // Traverse from the node up to the root
            while (curr_node != -1) {
                max_xor = Math.max(max_xor, val ^ curr_node);
                curr_node = parents[curr_node];
            }
            ans[i] = max_xor;
        }
        
        return ans;
    }
}
```
### Algorithm
1. Initialize an answer array `ans` with the same size as the `queries` array.
2. Iterate through each query `[node, val]` in the `queries` array.
3. For each query, initialize a variable `max_xor` to -1.
4. Start a traversal from the given `node` up to the root. Let the current node be `curr_node`.
5. In a loop, while `curr_node` is not -1 (the root's parent):
    a. Calculate the XOR difference: `current_xor = val ^ curr_node`.
    b. Update `max_xor = max(max_xor, current_xor)`.
    c. Move to the parent: `curr_node = parents[curr_node]`.
6. After the loop finishes (i.e., the root has been processed), store the final `max_xor` in the `ans` array at the corresponding query index.
7. After iterating through all queries, return the `ans` array.

## Offline Processing with DFS and Trie
This is a highly efficient approach that avoids redundant computations by processing queries offline. It combines a Depth First Search (DFS) traversal of the tree with a Trie (prefix tree). The Trie is used to efficiently find, for a given value `val`, the number in a set that produces the maximum XOR result. By performing a single DFS, we can answer all queries. At any point during the DFS at node `u`, the Trie will contain exactly the set of `u`'s ancestors, allowing us to answer queries for `u`.
**Time:** O((N + Q) * L)

- `N` is the number of nodes, `Q` is the number of queries, and `L` is the number of bits in the values (a constant, e.g., 18).
- Building the adjacency list and query map takes `O(N + Q)`.
- The DFS visits each node once. At each node, we perform one `insert` and one `remove` operation on the Trie, each taking `O(L)` time. Total for all nodes: `O(N * L)`.
- Each of the `Q` queries is processed once with a `findMaxXor` call, which takes `O(L)`. Total for all queries: `O(Q * L)`.
- The combined time complexity is `O(N + Q + N*L + Q*L)`, which simplifies to `O((N + Q) * L)`. · **Space:** O(N * L + Q)

- The Trie can store up to `N` numbers. In the worst case, the number of nodes in the Trie is `O(N * L)`, where `L` is the number of bits.
- The adjacency list requires `O(N)` space.
- The map for queries requires `O(Q)` space.
- The recursion stack for DFS can go up to `O(N)` in depth.
- The total space is dominated by the Trie, making it `O(N * L + Q)`.
**Pros:** Highly efficient with a time complexity that handles large constraints.; A generalizable technique for many types of path queries on trees.
**Cons:** Significantly more complex to implement compared to the brute-force approach.; Requires more memory due to the Trie data structure, adjacency list, and recursion stack.
### Explanation
The key insight to optimize this problem is to notice that queries for nodes in the same subtree share common ancestors. We can exploit this by processing queries in a structured way rather than one by one. This is a classic 'offline processing' technique.

We perform a single Depth First Search (DFS) from the root of the tree. We use a Trie data structure to keep track of the genetic values of all nodes on the path from the root to the current node in the DFS. 

**Algorithm Steps:**
1.  **Preprocessing**: We first convert the `parents` array into an adjacency list to represent the tree, which is more suitable for DFS. We also group the queries by the node they are associated with, so we can easily access all queries for a node `u` when our DFS visits `u`.
2.  **DFS Traversal**: We start a DFS from the root.
    -   When we enter a node `u`, we insert its genetic value `u` into the Trie. At this moment, the Trie contains the values of all of `u`'s ancestors.
    -   We then process all queries `[u, val]` that were originally for this node. For each such query, we use the Trie's `findMaxXor` function with `val` to find the best matching ancestor. The result is stored in our final answer array.
    -   Next, we recursively call the DFS for all children of `u`.
    -   After the recursive calls for all children have returned (i.e., we are about to backtrack from `u`), we remove `u`'s value from the Trie. This cleanup step is crucial because `u` is not an ancestor of its siblings or any nodes in other branches of the tree.

**Trie for Maximum XOR**: The Trie is built on the binary representation of the numbers. To find the maximum XOR for a value `val`, we traverse the Trie from the most significant bit (MSB) to the LSB. At each bit position, if the bit in `val` is `b`, we greedily try to find a number in the Trie that has the bit `1-b` at this position. This maximizes the resulting XOR bit by bit.

Here is a Java implementation of this approach:
```java
class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[2];
        int count = 0;
    }

    private static final int MAX_BIT = 17; // 2*10^5 < 2^18

    private void insert(TrieNode root, int num) {
        TrieNode curr = root;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
            curr.count++;
        }
    }

    private void remove(TrieNode root, int num) {
        TrieNode curr = root;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            curr = curr.children[bit];
            curr.count--;
        }
    }

    private int findMaxXor(TrieNode root, int num) {
        TrieNode curr = root;
        int maxXor = 0;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int targetBit = 1 - bit;
            if (curr.children[targetBit] != null && curr.children[targetBit].count > 0) {
                maxXor |= (1 << i);
                curr = curr.children[targetBit];
            } else {
                curr = curr.children[bit];
            }
        }
        return maxXor;
    }

    private void dfs(int u, List<List<Integer>> adj, TrieNode trieRoot, 
                     Map<Integer, List<int[]>> queriesByNode, int[] ans) {
        insert(trieRoot, u);
        if (queriesByNode.containsKey(u)) {
            for (int[] query : queriesByNode.get(u)) {
                ans[query[1]] = findMaxXor(trieRoot, query[0]);
            }
        }
        for (int v : adj.get(u)) {
            dfs(v, adj, trieRoot, queriesByNode, ans);
        }
        remove(trieRoot, u);
    }

    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int rootNode = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) rootNode = i;
            else adj.get(parents[i]).add(i);
        }

        Map<Integer, List<int[]>> queriesByNode = new HashMap<>();
        for (int i = 0; i < queries.length; i++) {
            queriesByNode.computeIfAbsent(queries[i][0], k -> new ArrayList<>()).add(new int[]{queries[i][1], i});
        }

        int[] ans = new int[queries.length];
        TrieNode trieRoot = new TrieNode();
        dfs(rootNode, adj, trieRoot, queriesByNode, ans);
        return ans;
    }
}
```
### Algorithm
1. **Preprocessing**:
   a. Build an adjacency list representation of the tree from the `parents` array for efficient DFS traversal.
   b. Group queries by their `node`. Use a `Map<Integer, List<int[]>>` where the key is `node` and the value is a list of `[val, original_index]` pairs.
2. **Trie Data Structure**:
   a. Define a `TrieNode` class with `children[2]` (for bits 0 and 1) and a `count` field to track how many numbers use that prefix.
   b. Implement `insert(num)`, `remove(num)`, and `findMaxXor(num)` methods for the Trie.
3. **DFS Traversal**:
   a. Initialize an empty Trie and an answer array `ans`.
   b. Find the root of the tree (node with parent -1).
   c. Start a recursive DFS from the root.
4. **DFS Function `dfs(u)`**:
   a. **Insert**: Call `trie.insert(u)` to add the current node's value to the set of ancestors.
   b. **Query**: Check if there are any queries for node `u`. If so, for each query `(val, index)`, compute `ans[index] = trie.findMaxXor(val)`.
   c. **Recurse**: Call `dfs(v)` for each child `v` of `u`.
   d. **Backtrack**: After returning from all children's recursive calls, call `trie.remove(u)` to remove the current node's value from the Trie. This ensures it's not considered an ancestor for sibling branches.
5. **Return** the `ans` array after the initial DFS call completes.

# Solutions
### Java

```java
class Solution {
  static final int MAXD = 17;
public
  int[] maxGeneticDifference(int[] parents, int[][] queries) {
    int n = parents.length;
    List<List<Integer>> edges = new ArrayList<List<Integer>>();
    for (int i = 0; i < n; i++)
      edges.add(new ArrayList<Integer>());
    int rootIndex = -1;
    for (int i = 0; i < n; i++) {
      if (parents[i] == -1)
        rootIndex = i;
      else
        edges.get(parents[i]).add(i);
    }
    List<List<int[]>> stored = new ArrayList<List<int[]>>();
    for (int i = 0; i < n; i++)
      stored.add(new ArrayList<int[]>());
    int queriesCount = queries.length;
    int[] ans = new int[queriesCount];
    for (int i = 0; i < queriesCount; i++)
      stored.get(queries[i][0]).add(new int[]{i, queries[i][1]});
    TrieNode root = new TrieNode();
    depthFirstSearch(ans, root, rootIndex, edges, stored);
    return ans;
  }
public
  void insert(TrieNode root, int x) {
    TrieNode curr = root;
    for (int i = MAXD; i >= 0; i--) {
      if ((x & (1 << i)) != 0) {
        if (curr.children[1] == null)
          curr.children[1] = new TrieNode();
        curr = curr.children[1];
      } else {
        if (curr.children[0] == null)
          curr.children[0] = new TrieNode();
        curr = curr.children[0];
      }
      curr.count++;
    }
  }
public
  int query(TrieNode root, int x) {
    int queryMax = 0;
    TrieNode curr = root;
    for (int i = MAXD; i >= 0; i--) {
      if ((x & (1 << i)) != 0) {
        if (curr.children[0] != null && curr.children[0].count > 0) {
          queryMax |= 1 << i;
          curr = curr.children[0];
        } else
          curr = curr.children[1];
      } else {
        if (curr.children[1] != null && curr.children[1].count > 0) {
          queryMax |= 1 << i;
          curr = curr.children[1];
        } else
          curr = curr.children[0];
      }
    }
    return queryMax;
  }
public
  void erase(TrieNode root, int x) {
    TrieNode curr = root;
    for (int i = MAXD; i >= 0; i--) {
      if ((x & (1 << i)) != 0)
        curr = curr.children[1];
      else
        curr = curr.children[0];
      curr.count--;
    }
  }
public
  void depthFirstSearch(int[] ans, TrieNode root, int node,
                        List<List<Integer>> edges, List<List<int[]>> stored) {
    insert(root, node);
    List<int[]> list = stored.get(node);
    for (int[] pair : list) {
      int index = pair[0], num = pair[1];
      ans[index] = query(root, num);
    }
    List<Integer> nextNodes = edges.get(node);
    for (int nextNode : nextNodes)
      depthFirstSearch(ans, root, nextNode, edges, stored);
    erase(root, node);
  }
} class TrieNode {
  int count;
  TrieNode[] children;
public
  TrieNode() {
    children = new TrieNode[2];
    count = 0;
  }
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/maximum-genetic-difference-query/ // Time: O(P + Q) // Space: O(P) struct TrieNode { TrieNode * next [ 2 ] = {}; int cnt = 0 ; }; class Solution { public: vector < int > maxGeneticDifference ( vector < int >& P , vector < vector < int >>& Q ) { int N = P . size (), M = Q . size (), rootIndex ; vector < vector < int >> G ( N ); for ( int i = 0 ; i < N ; ++ i ) { if ( P [ i ] != - 1 ) G [ P [ i ]]. push_back ( i ); else rootIndex = i ; } unordered_map < int , vector < int >> m ; for ( int i = 0 ; i < M ; ++ i ) m [ Q [ i ][ 0 ]]. push_back ( i ); TrieNode root ; auto getAnswer = [ & ]( TrieNode * node , int q ) { int ans = 0 ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = q >> i & 1 ; if ( node -> next [ 1 - b ] && node -> next [ 1 - b ] -> cnt ) { node = node -> next [ 1 - b ]; ans |= 1 << i ; } else node = node -> next [ b ]; } return ans ; }; vector < int > ans ( M ); function < void ( int ) > dfs = [ & ]( int u ) { auto node = & root ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = u >> i & 1 ; if ( ! node -> next [ b ]) node -> next [ b ] = new TrieNode (); node = node -> next [ b ]; node -> cnt ++ ; } if ( m . count ( u )) { for ( int index : m [ u ]) ans [ index ] = getAnswer ( & root , Q [ index ][ 1 ]); } for ( int v : G [ u ]) dfs ( v ); node = & root ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = u >> i & 1 ; node = node -> next [ b ]; node -> cnt -- ; } }; dfs ( rootIndex ); return ans ; } };
```