题目大意：有一棵$n$个点的树，第$i$个点权值为$w_i$，有两种操作：
- $1\;x\;y：$询问节点$x$的子树中与$y$异或结果的最大值
- $2\;x\;y\;z：$询问路径$x$到$y$上点与$z$异或结果最大值
题解：树剖，然后就可以把树上问题转化为序列上的问题，可持久化$Trie$即可
卡点：树剖判断条件错
C++ Code：
#include <algorithm>
#include <cstdio>
#define maxn 100010
#define M 30
#define N (maxn * (M + 2))
int head[maxn], cnt;
struct Edge {
int to, nxt;
} e[maxn << 1];
inline void addedge(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;
}
namespace Trie {
int V[N], nxt[N][2], idx;
void insert(int &rt, int x, int dep) {
nxt[++idx][0] = nxt[rt][0], nxt[idx][1] = nxt[rt][1], V[idx] = V[rt] + 1, rt = idx;
if (!~dep) return ;
insert(nxt[rt][x >> dep & 1], x, dep - 1);
}
int query(int L, int R, int x) {
int res = 0;
for (int i = M; ~i; i--) {
int tmp = x >> i & 1;
if (V[nxt[R][!tmp]] - V[nxt[L][!tmp]]) L = nxt[L][!tmp], R = nxt[R][!tmp], res |= 1 << i;
else L = nxt[L][tmp], R = nxt[R][tmp];
}
return res;
}
}
int n, m, w[maxn];
int rt[maxn];
int dfn[maxn], idx, dep[maxn], sz[maxn];
int fa[maxn], son[maxn], top[maxn];
void dfs1(int u) {
sz[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa[u]) {
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
if (!son[u] || sz[son[u]] < sz[v]) son[u] = v;
sz[u] += sz[v];
}
}
}
void dfs2(int u) {
dfn[u] = ++idx;
Trie::insert(rt[idx] = rt[idx - 1], w[u], M);
int v = son[u];
if (v) top[v] = top[u], dfs2(v);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
top[v] = v;
dfs2(v);
}
}
}
int query(int x, int y, int z) {
int res = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
res = std::max(res, Trie::query(rt[dfn[top[x]] - 1], rt[dfn[x]], z));
x = fa[top[x]];
}
if (dep[x] > dep[y]) std::swap(x, y);
res = std::max(res, Trie::query(rt[dfn[x] - 1], rt[dfn[y]], z));
return res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", w + i);
for (int i = 1, a, b; i < n; i++) {
scanf("%d%d", &a, &b);
addedge(a, b);
}
dfs1(1);
top[1] = 1;
dfs2(1);
while (m --> 0) {
int op, x, y, z;
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
printf("%d\n", Trie::query(rt[dfn[x] - 1], rt[dfn[x] + sz[x] - 1], y));
} else {
scanf("%d", &z);
printf("%d\n", query(x, y, z));
}
}
return 0;
}