嗑了半个多钟头,爽
$f$ 和 $g$ 是持久化 $trie$, $f$ 记录点 $u$ 到 根节点的上的所有数值。
对于操作 $2$,分别求,在 $x$ 到根节点和 $y$ 到根节点的路径中,与 $z$ 异或最大且其深度比 $p = lca(x, y)$ 要深的元素,相当于从一个区间中选一个数与 $x$ 的异或最大值,这步可用可持久化$trie$。
$g$ 就比较好说, 是 $dfs$序上的持久 $trie$, 用来求操作 $1$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10;
int n, m;
int w[N];
int h[N], e[N], ne[N], idx;
int id[N], cnt;
int fa[N][16], depth[N], sz[N];
struct Trie {
int root[N];
int tr[N][2], idx;
int max_dep[N];
void insert(int p, int q, int k, int d, int x) {
if (k < 0) {
max_dep[q] = d;
return ;
}
int v = x >> k & 1;
if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++ idx;
insert(tr[p][v], tr[q][v], k - 1, d, x);
max_dep[q] = max(max_dep[tr[q][0]], max_dep[tr[q][1]]);
}
int query(int p, int l, int x) {
int res = 0;
for (int i = 29; ~i; i -- ) {
int v = x >> i & 1;
if (max_dep[tr[p][v ^ 1]] >= l) res += 1 << i, p = tr[p][v ^ 1];
else p = tr[p][v];
}
return res;
}
}f, g;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int father) {
id[u] = ++ cnt, sz[u] = 1;
f.root[u] = ++ f.idx, g.root[cnt] = ++ g.idx, depth[u] = depth[father] + 1;
f.insert(f.root[father], f.root[u], 29, depth[u], w[u]);
g.insert(g.root[cnt - 1], g.root[cnt], 29, cnt, w[u]);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
fa[j][0] = u;
for (int k = 1; k <= 15; k ++ )
fa[j][k] = fa[fa[j][k - 1]][k - 1];
dfs(j, u);
sz[u] += sz[j];
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ ) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
f.root[0] = ++ f.idx, f.max_dep[0] = -1, f.insert(0, f.root[0], 29, 0, 0);
g.root[0] = ++ g.idx, g.max_dep[0] = -1, g.insert(0, g.root[0], 29, 0, 0);
dfs(1, 0);
while (m -- ) {
int t, x, y, z;
scanf("%d", &t);
if (t == 1) {
scanf("%d%d", &x, &y);
printf("%d\n", g.query(g.root[id[x] + sz[x] - 1], id[x], y));
}
else {
scanf("%d%d%d", &x, &y, &z);
int p = lca(x, y);
int v = max(f.query(f.root[x], depth[p], z), f.query(f.root[y], depth[p], z));
printf("%d\n", v);
}
}
return 0;
}