给定查询求e与节点d到根路径上所有节点XOR的最大值

核心原理 #

求单个整数与一组整数的最大异或值的经典实现是0-1字典树：从最高位到最低位贪心选择与查询数对应二进制位相反的分支，即可保证最终得到的异或值最大。针对本题中需要查询节点到根路径上所有节点的场景，可选择离线或在线两种方案实现。

离线解法（实现简单、空间开销低） #

适合可以提前收集到所有查询的场景：

• 预处理所有查询，按查询中的节点d分组，存储对应的e和查询下标，便于后续直接填充答案
• 对树做深度优先遍历：
  • 进入当前节点时，将当前节点编号插入0-1字典树
  • 处理所有绑定在当前节点的查询，用e在字典树中查询最大异或值，存入答案数组对应位置
  • 递归遍历当前节点的所有子节点
  • 递归返回前，将当前节点编号从0-1字典树中删除回退
• 遍历完成后直接按顺序输出答案数组即可

时间复杂度：假设节点编号为32位整数，总时间复杂度为O((N + C)*32)，其中N为树的总节点数，C为查询总次数。

在线解法（支持动态查询） #

适合需要随时响应查询、无法提前收集所有查询的场景：

• 基于可持久化0-1字典树实现，每个树节点对应一个字典树版本，版本中存储从根节点到当前节点路径上的所有节点编号
• 先对树做一次预遍历：每访问一个节点，就基于父节点的字典树版本插入当前节点编号，得到当前节点对应的字典树版本并保存
• 每次查询时，直接取出节点d对应的字典树版本，输入e查询最大异或值即可返回结果

时间复杂度和离线解法一致，空间复杂度为O(N*32)。

核心代码示例（C++ 离线解法） #

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int TRIE_SIZE = MAXN * 32;

// 0-1字典树定义
struct TrieNode {
    int cnt = 0;
    int next[2] = {0};
} tr[TRIE_SIZE];
int trie_idx = 0;

// 插入数值到字典树
void insert(int x) {
    int p = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (!tr[p].next[bit]) tr[p].next[bit] = ++trie_idx;
        p = tr[p].next[bit];
        tr[p].cnt++;
    }
}

// 从字典树删除数值
void remove(int x) {
    int p = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = (x >> i) & 1;
        p = tr[p].next[bit];
        tr[p].cnt--;
    }
}

// 查询和e的最大异或值
int query_max_xor(int e) {
    if (!tr[0].next[0] && !tr[0].next[1]) return 0;
    int p = 0, res = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = (e >> i) & 1;
        int want = bit ^ 1;
        if (tr[p].next[want] && tr[tr[p].next[want]].cnt > 0) {
            res += 1 << i;
            p = tr[p].next[want];
        } else {
            p = tr[p].next[bit];
        }
    }
    return res;
}

vector<int> tree[MAXN]; // 树的邻接表
vector<pair<int, int>> queries[MAXN]; // queries[d] = [(e, 答案下标)]
int ans[MAXN];

void dfs(int u, int fa) {
    insert(u);
    // 处理当前节点的所有查询
    for (auto &q : queries[u]) {
        ans[q.second] = query_max_xor(q.first);
    }
    // 遍历子节点
    for (int v : tree[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
    // 回退操作
    remove(u);
}

int main() {
    int N, C, root = 1;
    cin >> N;
    // 读入树边
    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    // 读入所有查询
    cin >> C;
    for (int i = 0; i < C; ++i) {
        int d, e;
        cin >> d >> e;
        queries[d].emplace_back(e, i);
    }
    // 从根节点开始DFS
    dfs(root, 0);
    // 输出答案
    for (int i = 0; i < C; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Pramit