Maximum genetic difference query

Array Hash Table Bit Manipulation Depth-First Search Trie

46.5% acceptance

Feb 25, 2026

415

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_genetic_difference(parents: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = parents.len();
    let mut children = vec![vec![]; n];
    let mut root = 0;
    for i in 0..n {
      if parents[i] == -1 {
        root = i;
      } else {
        children[parents[i] as usize].push(i);
      }
    }

    // Group queries by node
    let mut node_queries: Vec<Vec<(i32, usize)>> = vec![vec![]; n];
    for (idx, q) in queries.iter().enumerate() {
      node_queries[q[0] as usize].push((q[1], idx));
    }

    // Binary trie
    let max_bits = 18; // 2*10^5 < 2^18
    let mut trie = vec![[0i32; 2]; 1];
    let mut cnt = vec![0i32; 1];
    let mut trie_size = 1;

    let mut ans = vec![0i32; queries.len()];

    // DFS with trie insert/remove
    let mut stack: Vec<(usize, bool)> = vec![(root, false)];
    while let Some((node, leaving)) = stack.pop() {
      if leaving {
        // Remove node from trie
        let mut idx = 0;
        for bit in (0..max_bits).rev() {
          let b = ((node >> bit) & 1) as usize;
          let next = trie[idx][b] as usize;
          cnt[next] -= 1;
          idx = next;
        }
        continue;
      }

      // Insert node into trie
      let mut idx = 0;
      for bit in (0..max_bits).rev() {
        let b = ((node >> bit) & 1) as usize;
        if trie[idx][b] == 0 {
          trie.push([0; 2]);
          cnt.push(0);
          trie[idx][b] = trie_size as i32;
          trie_size += 1;
        }
        idx = trie[idx][b] as usize;
        cnt[idx] += 1;
      }

      // Answer queries for this node
      for &(val, qi) in &node_queries[node] {
        let mut result = 0;
        let mut idx = 0;
        for bit in (0..max_bits).rev() {
          let b = ((val >> bit) & 1) as usize;
          let want = 1 - b; // want opposite bit for max XOR
          if trie[idx][want] != 0 && cnt[trie[idx][want] as usize] > 0 {
            result |= 1 << bit;
            idx = trie[idx][want] as usize;
          } else {
            idx = trie[idx][b] as usize;
          }
        }
        ans[qi] = result;
      }

      // Push leaving marker, then children
      stack.push((node, true));
      for &child in &children[node] {
        stack.push((child, false));
      }
    }

    ans
  }
}