[TJOI2018] 异或

题意

树上有 $n$ 个节点，每个点有权值 $v_i$ 。 $q$ 次询问：

1 x z：在 $x$ 的子树中取一个点的权值，与 $z$ 异或的最大值；
2 x y z：在 $x$ 到 $y$ 的简单路径上取一个点的权值，与 $z$ 异或的最大值。

数据范围： $n, q \leqslant 10^5$ ， $v_i, z < 2^{30}$ 。

思路

一句话本质：异或最大值 = 从高位到低位贪心找相反位，01-Trie 负责 $O(30)$ 回答；真正的难点是把"子树"和"路径"两种树上的点集翻译成可持久化 Trie 的版本差。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 12:30
 * update_at: 2026-08-05 12:30
 */
// brute.cpp：小数据暴力解，子树用 DFS 收集节点，路径用 DFS 找路，逐个取异或最大值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, q;
int val[MAXN];
vector<int> g[MAXN];
int parent_node[MAXN];   // 每个节点的父节点（根为 0）

vector<int> path_nodes;

// 求父节点数组
void dfs_parent(int u, int f) {
    parent_node[u] = f;
    for (int v : g[u])
        if (v != f) dfs_parent(v, u);
}

// 收集 u 的子树节点（不经过父节点）
void collect_subtree(int u, int f) {
    path_nodes.push_back(u);
    for (int v : g[u])
        if (v != f) collect_subtree(v, u);
}

// 找 x 到 y 的路径节点，找到返回 true
bool find_path(int u, int target, int f) {
    path_nodes.push_back(u);
    if (u == target) return true;
    for (int v : g[u])
        if (v != f && find_path(v, target, u)) return true;
    path_nodes.pop_back();
    return false;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_parent(1, 0);

    for (int t = 0; t < q; t++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, z;
            cin >> x >> z;
            path_nodes.clear();
            collect_subtree(x, parent_node[x]);   // 排除父节点，只收集真子树
            int ans = 0;
            for (int u : path_nodes) ans = max(ans, val[u] ^ z);
            cout << ans << '\n';
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            path_nodes.clear();
            find_path(x, y, 0);
            int ans = 0;
            for (int u : path_nodes) ans = max(ans, val[u] ^ z);
            cout << ans << '\n';
        }
    }

    return 0;
}

下面是同一个暴力的 Pythonic 写法：一次 BFS 求出父节点后，子树用"从 x 不经过父节点"收集，路径用两条父链在 lca 汇合：

Pythonic 暴力版本

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
"""brute.py：P4592 小数据暴力，递归收集目标节点后逐个异或取最大值。"""
import sys


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    w = [0] + list(map(int, input().split()))
    g = [[] for _ in range(n + 1)]
    # 一行版：append 返回 None，用 or 链式执行第二个 append（每次迭代解包一个新的 map）
    # [g[u].append(v) or g[v].append(u) for _ in range(n - 1) for u, v in [map(int, input().split())]]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)

    ns = []  # 当前查询的目标节点

    par = [0] * (n + 1)  # 父节点
    order = [1]
    # 一行版：setdefault 首次设置返回 u，回父边返回旧值被自动过滤（依赖树无环 + par[1]=0）
    # [order.append(v) for u in order for v in g[u] if par.setdefault(v, u) == u]
    for u in order:
        for v in g[u]:
            if v != par[u]:
                par[v] = u
                order.append(v)

    # 一行版 collect：lambda 返回 (append, 列表推导) 元组，递归时名字已绑定
    # collect = lambda u, f: (ns.append(u), [collect(v, u) for v in g[u] if v != f])
    def collect(u, f):  # 收集子树：从 u 出发不经过父 f
        ns.append(u)
        for v in g[u]:
            if v != f:
                collect(v, u)

    def path(u, target, f):  # 找 u 到 target 的路径，找到返回 True
        ns.append(u)
        if u == target:
            return True
        for v in g[u]:
            if v != f and path(v, target, u):
                return True
        ns.pop()  # 回溯

    out = []
    for _ in range(q):
        a = list(map(int, input().split()))
        ns.clear()
        if a[0] == 1:
            _, x, z = a
            collect(x, par[x])
        else:
            _, x, y, z = a
            path(x, y, 0)
        out.append(str(max(w[u] ^ z for u in ns)))  # 逐个异或取最大
    print("\n".join(out))


if __name__ == "__main__":
    main()

暴力每次查询 DFS 收集目标点集，再逐个异或取最大值， $O(qn)$ 显然不行。卡点有两层：集合怎么取、取到后怎么快速求最大异或。

异或最大值依赖集合的什么结构？

要最大化 $v \oplus z$ ，从最高位到最低位贪心：第 $b$ 位希望结果是 $1$ ，即希望集合中存在"第 $b$ 位与 $z$ 相反"的点。每一步只关心集合里有没有走某个分支的点。如果集合能表示成"两个版本之差"，可持久化 01-Trie 就能在 $O(30)$ 内回答： $sz[分支][版本_r] - sz[分支][版本_l] > 0$ 说明分支非空。

所以问题变成：子树和路径，能不能表示成版本差？

子树能表示成版本差吗？

能。DFS 序的关键性质：一个子树在 dfn 序上是连续区间 $[dfn[x], dfn[x] + size[x] - 1]$ 。按 dfn 顺序把点权依次插入可持久化 Trie，第 $i$ 个版本就是"前 $i$ 个 dfn 节点"——子树查询变成区间版本差：

text

1子树(x) 的点集 = 版本[dfn[x]+size[x]-1] − 版本[dfn[x]-1]

路径也能表示成版本差吗？

路径不是区间，但可以拆成"根到点的链"。 $x$ 到 $y$ 的路径 = 根到 $x$ 的链 ∪ 根到 $y$ 的链 − 根到 $lca$ 的链 − 根到 $fa[lca]$ 的链：

text

1路径(x,y) = 版本[x] + 版本[y] − 版本[lca] − 版本[fa[lca]]

这个容斥逐点验证： $lca$ 本身在两条链里各出现一次，减一条链后还剩一次（ $1+1-1=1$ ）； $lca$ 上方的点在两条链里都有，被两个负版本各减一次（ $1+1-1-1=0$ ）； $lca$ 下方的点只属于其中一条链（ $1+0-0-0=1$ ）。每个点恰好被计数一次。

根到点的链版本怎么建？

DFS 时继承父节点版本，再插入当前点的权值：版本[u] = insert(版本[fa[u]], v[u])。沿根到叶的方向，版本天然是"深度前缀"，和可持久化的"前缀版本"完全一致。

查询时四个版本怎么用？

四版本差 $(a + b - c - d)$ ：贪心每步统计目标分支的计数 = $sz[ch[a]] + sz[ch[b]] - sz[ch[c]] - sz[ch[d]]$ ，大于 $0$ 就走进这个分支。子树查询是它的特例（ $2$ 版本差）。

两类版本（dfn 序、根链）插入逻辑完全相同，共用同一个节点池。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 12:30
 * update_at: 2026-08-05 12:30
 */
// 可持久化 01-Trie：
//   子树查询：DFS 序把子树变成连续区间，在 dfn 序版本 Trie 上做区间异或最大值
//   路径查询：根到节点的版本 Trie 做四版本差（x + y - lca - fa[lca]）
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXLOG = 30;                       // 值 < 2^30，处理第 0..29 位
const int MAXNODE = MAXN * 2 * (MAXLOG + 1); // 两个逻辑 Trie 共用一个节点池

int n, q;
int val[MAXN];          // 节点权值

// 链式前向星
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 可持久化 01-Trie 节点池
int ch[2][MAXNODE];   // 两个孩子
int sz[MAXNODE];      // 该节点子树中的元素个数
int tot;              // 节点池大小

// 在旧版本 old 上插入 x，返回新版本根
int trie_insert(int old, int x) {
    int now = ++tot;
    int cur = now, pre = old;
    sz[cur] = sz[pre] + 1;
    for (int b = MAXLOG - 1; b >= 0; b--) {
        int c = (x >> b) & 1;
        ch[c][cur] = ++tot;
        ch[!c][cur] = ch[!c][pre];   // 未改变的分支直接指向旧版本
        cur = ch[c][cur];
        pre = ch[c][pre];
        sz[cur] = sz[pre] + 1;
    }
    return now;
}

// 查询版本差区间 (lv, rv] 内与 x 异或的最大值
int trie_query_interval(int lv, int rv, int x) {
    int res = 0;
    for (int b = MAXLOG - 1; b >= 0; b--) {
        int c = (x >> b) & 1, want = c ^ 1;   // 优先走相反位
        if (sz[ch[want][rv]] - sz[ch[want][lv]] > 0) {
            res |= (1 << b);
            lv = ch[want][lv];
            rv = ch[want][rv];
        } else {
            lv = ch[c][lv];
            rv = ch[c][rv];
        }
    }
    return res;
}

// 查询四版本差 (a + b - c - d) 内与 x 异或的最大值（路径查询用）
int trie_query_path(int a, int b, int c, int d, int x) {
    int res = 0;
    for (int bit = MAXLOG - 1; bit >= 0; bit--) {
        int w = (x >> bit) & 1, want = w ^ 1;
        int cnt = sz[ch[want][a]] + sz[ch[want][b]] - sz[ch[want][c]] - sz[ch[want][d]];
        if (cnt > 0) {
            res |= (1 << bit);
            a = ch[want][a]; b = ch[want][b]; c = ch[want][c]; d = ch[want][d];
        } else {
            a = ch[w][a]; b = ch[w][b]; c = ch[w][c]; d = ch[w][d];
        }
    }
    return res;
}

// DFS 序、子树大小、深度、倍增、根到节点的版本 Trie
int dfn[MAXN], dfn_node[MAXN], sub_size[MAXN], dfn_cnt;
int depth[MAXN], fa[MAXN][18];
int root_path[MAXN];   // root_path[x]：根到 x 的路径上所有权值的版本
int root_dfn[MAXN];    // root_dfn[i]：dfn 序前 i 个节点的版本

// 显式栈迭代 DFS，避免链式数据递归爆栈
struct StackItem {
    int u, f, e;   // 当前节点、父节点、下一条要处理的边
};
StackItem stk[MAXN];
int stk_top;

void dfs1() {
    stk_top = 1;
    stk[1] = {1, 0, head[1]};

    // 进入根节点 1
    dfn[1] = ++dfn_cnt;
    dfn_node[dfn_cnt] = 1;
    sub_size[1] = 1;
    depth[1] = 1;
    fa[1][0] = 0;
    root_path[1] = trie_insert(0, val[1]);

    while (stk_top > 0) {
        int u = stk[stk_top].u;
        int f = stk[stk_top].f;
        int e = stk[stk_top].e;

        if (e == 0) {   // 所有边处理完：离开 u，把子树大小合并给父
            if (f != 0) sub_size[f] += sub_size[u];
            stk_top--;
            continue;
        }

        stk[stk_top].e = nxt[e];   // 取走当前边
        int v = to[e];
        if (v == f) continue;

        // 进入子节点 v
        stk_top++;
        stk[stk_top] = {v, u, head[v]};
        dfn[v] = ++dfn_cnt;
        dfn_node[dfn_cnt] = v;
        sub_size[v] = 1;
        depth[v] = depth[u] + 1;
        fa[v][0] = u;
        for (int k = 1; k <= 17; k++)
            fa[v][k] = fa[fa[v][k - 1]][k - 1];
        root_path[v] = trie_insert(root_path[u], val[v]);
    }
}

// 倍增求 LCA
int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 17; k >= 0; k--)
        if (depth[fa[x][k]] >= depth[y]) x = fa[x][k];
    if (x == y) return x;
    for (int k = 17; k >= 0; k--)
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    dfs1();   // 版本 0（tot=0）表示空 Trie，root_path[0] = 0

    // 按 dfn 序建"子树版本"的 Trie
    for (int i = 1; i <= n; i++)
        root_dfn[i] = trie_insert(root_dfn[i - 1], val[dfn_node[i]]);

    for (int t = 0; t < q; t++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, z;
            cin >> x >> z;
            int l = dfn[x], r = dfn[x] + sub_size[x] - 1;   // 子树对应 dfn 区间
            cout << trie_query_interval(root_dfn[l - 1], root_dfn[r], z) << '\n';
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            int w = lca(x, y);
            // 路径 = (根到 x) + (根到 y) - (根到 lca) - (根到 fa[lca])
            cout << trie_query_path(root_path[x], root_path[y],
                                    root_path[w], root_path[fa[w][0]], z) << '\n';
        }
    }

    return 0;
}

复杂度

预处理：可持久化 Trie 插入 $O(30n)$ ，倍增 LCA $O(n \log n)$ 。子树查询 $O(30)$ ；路径查询 $O(\log n + 30)$ （LCA + Trie）。空间：节点池 $O(30n)$ ，倍增表 $O(n \log n)$ 。

总结

本题的卡点不是 01-Trie 本身，而是把树上的点集翻译成版本差：

子树是连续区间 → dfn 版本差；
路径拆成根链 → 四版本容斥。

所有树上"点集查询"都可以先问自己：这个集合能不能表示成几个"前缀版本"的组合？能，就用可持久化结构。

图示解析

这张图展示两种查询分别如何变成版本差：

text

1
2
3
4
5
6
7
8
9
10
11子树查询：dfn 区间                     路径查询：四版本容斥

树（以 1 为根）                       路径 4 → 7，lca = 1
1 ─┬─ 2 ─ 4                           根链(4) = {1,2,4}
   └─ 3 ─┬─ 5                        根链(7) = {1,3,7}
         ├─ 6                         根链(1) = {1}
         └─ 7                         根链(fa[1]=0) = {}

子树(3) = {3,5,6,7}                   {1,2,4}∪{1,3,7}−{1}−{}
  dfn 序: 1 2 4 3 5 6 7              = {2,4,3,7} ✓ 恰好是路径上的点
  子树(3) 对应 dfn[4..7] 连续区间

读图方法：左边，子树在 dfn 数组上永远是一整段连续下标，这是"区间版本差"的前提；右边，路径集合等于两条根链的并减去两段重复的公共链，每个点恰好被计数一次，这是"四版本容斥"的依据。

目录

题意

思路

代码

复杂度

总结

图示解析