)
这道题是树上离线查询 + 0-1 Trie 的经典应用，核心在于利用 DFS 回溯时动态维护 Trie，并离线处理所有查询。
解题思路
1. 问题分析
· 给定一棵树，parents[i] 是节点 i 的父节点（根节点的父节点为 -1）
· 每次查询 [node, val]，需要找到 node 到根路径上某个节点与 val 的最大异或值
2. 核心思想
· 离线处理：将所有查询按节点分组，在 DFS 遍历树时处理
· 可回溯 Trie：DFS 进入节点时插入该节点值，离开时删除（或使用计数）
· 最大异或：对每个查询 val，在 Trie 中找与 val 异或最大的值
3. Trie 设计
使用带删除计数的 0-1 Trie，支持：
· insert(num)：插入一个数
· remove(num)：删除一个数（计数 -1）
· maxXor(val)：查询与 val 异或的最大值
Java 代码
```java
class Solution {
// 0-1 Trie 节点
class TrieNode {
TrieNode[] children = new TrieNode[2];
int count = 0; // 经过该节点的数量
}
class Trie {
TrieNode root = new TrieNode();
void insert(int num) {
TrieNode node = root;
for (int i = 17; i >= 0; i--) { // 2^17 > 10^5
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
node.count++;
}
}
void remove(int num) {
TrieNode node = root;
for (int i = 17; i >= 0; i--) {
int bit = (num >> i) & 1;
node = node.children[bit];
node.count--;
}
}
int maxXor(int val) {
TrieNode node = root;
int result = 0;
for (int i = 17; i >= 0; i--) {
int bit = (val >> i) & 1;
int opposite = bit ^ 1;
if (node.children[opposite] != null &&
node.children[opposite].count > 0) {
result |= (1 << i);
node = node.children[opposite];
} else {
node = node.children[bit];
}
}
return result;
}
}
public int[] maxGeneticDifference(int[] parents, int[][] queries) {
int n = parents.length;
// 1. 建树
List<Integer>[] tree = new List[n];
for (int i = 0; i < n; i++) {
tree[i] = new ArrayList<>();
}
int root = -1;
for (int i = 0; i < n; i++) {
if (parents[i] == -1) {
root = i;
} else {
tree[parents[i]].add(i);
}
}
// 2. 离线查询分组
int q = queries.length;
List<int[]>[] nodeQueries = new List[n];
for (int i = 0; i < n; i++) {
nodeQueries[i] = new ArrayList<>();
}
for (int i = 0; i < q; i++) {
int node = queries[i][0];
int val = queries[i][1];
nodeQueries[node].add(new int[]{val, i});
}
// 3. DFS + 回溯 Trie
int[] result = new int[q];
Trie trie = new Trie();
dfs(root, tree, nodeQueries, trie, result);
return result;
}
private void dfs(int node, List<Integer>[] tree,
List<int[]>[] nodeQueries,
Trie trie, int[] result) {
// 进入节点：插入当前节点值
trie.insert(node);
// 处理该节点上的所有查询
for (int[] query : nodeQueries[node]) {
int val = query[0];
int idx = query[1];
result[idx] = trie.maxXor(val);
}
// 递归子节点
for (int child : tree[node]) {
dfs(child, tree, nodeQueries, trie, result);
}
// 离开节点：删除当前节点值
trie.remove(node);
}
}
```
复杂度分析
· 时间复杂度：O((n + q) * B)，其中 B 是 Trie 的深度（这里取 18，因为 2^17 > 10^5）
· 空间复杂度：O(n * B + q)，Trie 每个节点最多 18 层，每层可能创建新节点
关键点说明
要点 说明
离线查询 将查询按节点分组，DFS 到节点时立即处理其所有查询
回溯 Trie insert 进入，remove 退出，保证 Trie 中始终是当前路径上的值
计数删除 使用 count 字段避免实际删除节点，支持重复值
异或最大 在 Trie 中尽量走与当前位相反的路径
运行示例
```java
int[] parents = {-1,0,1,1};
int[][] queries = {{0,2},{3,2},{2,5}};
// 输出: [2,3,7]
```
Trie 深度设为 17（覆盖 10^5），完全满足数据范围要求。
