What is the main idea behind Maximum Genetic Difference Query?

It computes the maximum XOR between a query value and any ancestor along a node's path to the root using array scanning plus a trie for efficiency.

Why do we need a trie in this problem?

The trie allows fast computation of the maximum XOR along the current path without scanning all ancestors for every query.

Can we solve it without a trie?

Yes, but scanning all ancestors for each query results in O(N*Q) time, which is inefficient for large trees.

How does backtracking affect the solution?

Backtracking ensures only active path nodes remain in the trie, preventing interference from unrelated branches when computing XOR.

What is a common mistake when implementing this solution?

A frequent error is forgetting to remove nodes from the trie during DFS backtracking, leading to incorrect maximum XOR results.

#1938

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

查询最大基因差

给你一棵 n 个节点的有根树，节点编号从 0 到 n - 1 。每个节点的编号表示这个节点的独一无二的基因值（也就是说节点 x 的基因值为 x ）。两个基因值的基因差是两者的异或和。给你整数数组 parents ，其中 parents[i] 是节点 i 的父节点。如果节点 x 是树的根…

数组哈希表位运算深度优先搜索字典树

题目描述

给你一棵 n 个节点的有根树，节点编号从 0 到 n - 1 。每个节点的编号表示这个节点的 独一无二的基因值 （也就是说节点 x 的基因值为 x）。两个基因值的 基因差 是两者的 异或和 。给你整数数组 parents ，其中 parents[i] 是节点 i 的父节点。如果节点 x 是树的根，那么 parents[x] == -1 。

给你查询数组 queries ，其中 queries[i] = [node_i, val_i] 。对于查询 i ，请你找到 val_i 和 p_i 的 最大基因差 ，其中 p_i 是节点 node_i 到根之间的任意节点（包含 node_i 和根节点）。更正式的，你想要最大化 val_i XOR p_i。

请你返回数组 ans ，其中 ans[i] 是第 i 个查询的答案。

示例 1：

输入：parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
输出：[2,3,7]
解释：查询数组处理如下：
- [0,2]：最大基因差的对应节点为 0 ，基因差为 2 XOR 0 = 2 。
- [3,2]：最大基因差的对应节点为 1 ，基因差为 2 XOR 1 = 3 。
- [2,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。

示例 2：

输入：parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
输出：[6,14,7]
解释：查询数组处理如下：
- [4,6]：最大基因差的对应节点为 0 ，基因差为 6 XOR 0 = 6 。
- [1,15]：最大基因差的对应节点为 1 ，基因差为 15 XOR 1 = 14 。
- [0,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。

提示：

2 <= parents.length <= 10⁵
对于每个不是根节点的 i ，有 0 <= parents[i] <= parents.length - 1 。
parents[root] == -1
1 <= queries.length <= 3 * 10⁴
0 <= node_i <= parents.length - 1
0 <= val_i <= 2 * 10⁵

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	complexity is roughly O(N * log M + Q * log M), where N is the number of nodes, Q is the number of queries, and M is the maximum genetic value, due to trie insertions and XOR lookups. Space complexity is O(N * log M) for the trie storing active path values.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for understanding of XOR properties and trie usage in path queries.
question_mark
Expect the candidate to manage insertion and removal in the trie to maintain correct path context.
question_mark
Interested in whether the solution handles large trees and query sets efficiently with DFS and hashing.

warning

常见陷阱

外企场景

error
Failing to remove nodes from the trie during backtracking, which produces incorrect XOR results.
error
Attempting to compute maximum XOR without a trie, leading to O(N*Q) complexity.
error
Mismanaging the mapping between node indices and their genetic values when scanning paths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Queries limited to leaf nodes instead of arbitrary nodes.
arrow_right_alt
Return the minimum genetic difference instead of the maximum.
arrow_right_alt
Allow dynamic updates to node genetic values, requiring persistent trie structures.

help

常见问题

外企场景

继续练习

#1178 猜字谜 #1993 树上的操作 #1994 好子集的数目