可持久化 01-Trie 与树上差分

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

const int MAXN = 100005;
const int MAXM = 20000005; // 可持久化Trie节点数
const int BITS = 30;       // 权值 <= 2^30，最高位索引30

int n, Q;
int v[MAXN];
vector<int> G[MAXN];

// ---------- LCA 倍增 ----------
int dep[MAXN], fa[MAXN][20];
void dfs_lca(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i < 20; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for (int v : G[u]) {
        if (v == p) continue;
        dfs_lca(v, u);
    }
}
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

// ---------- 可持久化 Trie ----------
struct Node {
    int ch[2];
    int cnt;
} trie[MAXM];
int tot;

int newnode() {
    ++tot;
    trie[tot].ch[0] = trie[tot].ch[1] = 0;
    trie[tot].cnt = 0;
    return tot;
}

// 在old版本的基础上插入数x，返回新版本根
int insert(int old, int x) {
    int now = newnode();
    int cur = now;
    int old_cur = old;
    for (int i = BITS; i >= 0; i--) {
        int b = (x >> i) & 1;
        trie[cur].ch[b^1] = trie[old_cur].ch[b^1];
        trie[cur].ch[b] = newnode();
        trie[cur].cnt = trie[old_cur].cnt + 1;
        cur = trie[cur].ch[b];
        old_cur = trie[old_cur].ch[b];
    }
    trie[cur].cnt = trie[old_cur].cnt + 1;
    return now;
}

// 在版本r和版本l的差分Trie上，查询与y异或的最大值
int query_max(int r, int l, int y) {
    int res = 0;
    for (int i = BITS; i >= 0; i--) {
        int b = (y >> i) & 1;
        int want = b ^ 1;
        int c_want = trie[trie[r].ch[want]].cnt - trie[trie[l].ch[want]].cnt;
        if (c_want > 0) {
            res |= (1 << i);
            r = trie[r].ch[want];
            l = trie[l].ch[want];
        } else {
            r = trie[r].ch[b];
            l = trie[l].ch[b];
        }
    }
    return res;
}

// 在四个版本的差分上查询与z异或的最大值
// 路径x-y = path[x] + path[y] - path[lca] - path[fa[lca]]
int query_path(int x, int y, int lca, int flca, int z) {
    int rx = x, ry = y, rl = lca, rf = flca;
    int res = 0;
    for (int i = BITS; i >= 0; i--) {
        int b = (z >> i) & 1;
        int want = b ^ 1;
        int c_want = trie[trie[rx].ch[want]].cnt
                   + trie[trie[ry].ch[want]].cnt
                   - trie[trie[rl].ch[want]].cnt
                   - trie[trie[rf].ch[want]].cnt;
        if (c_want > 0) {
            res |= (1 << i);
            rx = trie[rx].ch[want];
            ry = trie[ry].ch[want];
            rl = trie[rl].ch[want];
            rf = trie[rf].ch[want];
        } else {
            rx = trie[rx].ch[b];
            ry = trie[ry].ch[b];
            rl = trie[rl].ch[b];
            rf = trie[rf].ch[b];
        }
    }
    return res;
}

// ---------- DFS序Trie（用于子树查询） ----------
int dfn[MAXN], out[MAXN], timer;
int root_dfn[MAXN];

void dfs_dfn(int u, int p) {
    dfn[u] = ++timer;
    root_dfn[timer] = insert(root_dfn[timer-1], v[u]);
    for (int v : G[u]) {
        if (v == p) continue;
        dfs_dfn(v, u);
    }
    out[u] = timer;
}

// ---------- 路径Trie（用于路径查询） ----------
int root_path[MAXN];

void dfs_path(int u, int p) {
    root_path[u] = insert(root_path[p], v[u]);
    for (int v : G[u]) {
        if (v == p) continue;
        dfs_path(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> Q;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // 预处理LCA
    dep[0] = -1;
    dfs_lca(1, 0);

    // 初始化Trie
    tot = 0;
    int empty_node = newnode();
    root_dfn[0] = empty_node;
    root_path[0] = empty_node;

    // 构建DFS序Trie
    timer = 0;
    dfs_dfn(1, 0);

    // 构建路径Trie
    dfs_path(1, 0);

    // 处理查询
    while (Q--) {
        int op, x, y, z;
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            int l = dfn[x], r = out[x];
            int ans = query_max(root_dfn[r], root_dfn[l-1], y);
            cout << ans << "\n";
        } else {
            cin >> x >> y >> z;
            int lca = LCA(x, y);
            int flca = fa[lca][0];
            int ans = query_path(root_path[x], root_path[y], root_path[lca], root_path[flca], z);
            cout << ans << "\n";
        }
    }

    return 0;
}

算法解析

本题的核心在于将树上问题转化为区间问题，并利用可持久化 01-Trie​ 维护前缀信息以支持异或最大值查询。

1. 前置知识：01-Trie 与可持久化
   01-Trie：将数字按二进制位（从高位到低位）插入字典树。查询与 x 异或的最大值时，贪心地选择与 x 当前位相反的分支。
   可持久化：每次插入新节点时，复制路径上的节点，从而保留历史版本。这样，版本 r 与版本 l−1 的 Trie 相减，即可得到区间 [l,r] 内所有数的集合。
2. 操作 1：子树查询

子树查询是经典的 DFS 序 + 可持久化 Trie​ 问题。

转化：通过一次 DFS，求出每个节点的入栈时间戳 dfn[u] 和出栈时间戳 out[u]。那么节点 x 的子树恰好对应区间 [dfn[x],out[x]]。
构建：按照 DFS 序依次将节点权值插入可持久化 Trie。记 root_dfn[i] 为插入第 i 个节点后的 Trie 根节点。
查询：查询区间 [dfn[x],out[x]] 时，利用 root_dfn[out[x]] 和 root_dfn[dfn[x]−1] 进行差分，在得到的 Trie 上贪心求与 y 的异或最大值。
3. 操作 2：路径查询

路径查询需要利用 LCA​ 和 树上差分​ 的思想。

构建：我们需要另一套可持久化 Trie，按照“根到节点”的路径构建。记 root_path[u] 为从根节点 1 到节点 u 的路径上所有节点权值构成的 Trie。
转化：对于路径 x→y，设其 LCA 为 l，父亲为 f。路径上的权值集合可以表示为：
{1→x}∪{1→y}−{1→l}−{1→f}
查询：在四个版本 root_path[x],root_path[y],root_path[l],root_path[f] 的 Trie 上同时进行差分，统计每一位上 0 和 1 的数量，然后贪心选择与 z 当前位相反的方向。
4. 关键细节
两套 Trie：必须建立两套独立的可持久化 Trie，一套用于子树（基于 DFS 序），一套用于路径（基于根到节点）。
LCA 处理：使用倍增法预处理，以便 O(logn) 查询 LCA 及其父节点。
空间复杂度：每个插入操作最多新增 O(logV) 个节点（V 为值域），总空间约为 O((n+Q)logV)，需开足够大的数组（通常 n×32×2 以上）。
复杂度分析
时间复杂度：O((n+Q)logV)，其中 V=2的30次方。
空间复杂度：O(nlogV)。