by kintsgi @ 2022-07-19 21:21:32
@[hank0402](/user/482642) 试试 `assert(下标 >= 0);`
by Yansuan_HCl @ 2022-07-19 21:41:51
哦，我是【】，改完之后 WA 了qwq：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define debug(a, n)\
printf(#a ":");\
for(int i = 1; i <= n; ++i) cout << a[i] << ' ';\
cout << '\n';
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
// int x;
// scanf("%d", &x);
// return x;
}
const int N = 1e6 + 10;
const int T = 2e7 + 10;
int n, q, val[N];
vector<int> g[N << 1];
int ch[T][2], siz[T], tot, totd/*in dfs*/, L[N], R[N], dep[N], fa[25][N];
int type1[N], type2[N];
void cop(int x, int y) {
ch[x][0] = ch[y][0];
ch[x][1] = ch[y][1];
siz[x] = siz[y];
}
void Insert(int &rt, int x, int Bit) {
++tot;
cop(tot, rt); rt = tot;
++siz[rt];
if(Bit >= 0) {
int turn = ((x >> Bit) & 1);
Insert(ch[rt][turn], x, Bit - 1);
}
}
void dfs(int x, int from) {
++totd;
fa[0][x] = from;
dep[x] = dep[fa[0][x]] + 1;
L[x] = totd;
type1[totd] = type1[totd - 1]; /*dfn*/
Insert(type1[totd], val[x], 29);
type2[x] = type2[from]; /*paths*/
Insert(type2[x], val[x], 29);
for(int t = 1; (1 << t) < dep[x] && t <= 20; ++t) {
fa[t][x] = fa[t - 1][fa[t - 1][x]];
}
for(int y : g[x]) {
if(y == from) continue;
dfs(y, x);
}
R[x] = totd;
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20, d = dep[x] - dep[y]; i >= 0; --i) {
if(d <= 0) break;
int ups = (1 << i);
while(d >= ups) {
x = fa[i][x];
d -= ups;
}
}
if(x == y) {
return x;
}
for(int i = 20; i >= 0; --i) {
if(!fa[i][x] || !fa[i][y] || fa[i][x] == fa[i][y]) continue;
x = fa[i][x]; y = fa[i][y];
}
return fa[0][x]; //
}
int query(int lp, int rp, int x, int Bit) {
if(Bit <= 0) return 0;
int turn = ((x >> Bit) & 1) ^ 1;
// cout << turn << endl;
if(siz[ch[lp][turn]] > siz[ch[rp][turn]]) {
// puts("abc");
return query(ch[lp][turn], ch[rp][turn], x, Bit - 1) | (1 << Bit);
}
else {
// puts("xyz");
turn = 1 - turn;
return query(ch[lp][turn], ch[rp][turn], x, Bit - 1);
}
}
int main() {
n = read(); q = read();
for(int i = 1; i <= n; ++i) val[i] = read();
for(int i = 1; i < n; ++i) {
int _u, _v;
_u = read();
_v = read();
g[_u].push_back(_v);
g[_v].push_back(_u);
}
dfs(1, 0);
// debug(dep, n);
// debug(L, n);
// debug(R, n);
// debug(val, n);
// debug(siz, n);
while(q --){
int opt, x, y, z;
opt = read(); x = read(); y = read();
if(opt == 1) {
printf("%d\n", query(type1[R[x]], type1[L[x] - 1], y, 29));
}
else {
z = read();
int father = lca(x, y);
father = fa[0][father];
int res1 = query(type2[x], type2[father], z, 29);
int res2 = query(type2[y], type2[father], z, 29);
printf("%d\n", max(res1, res2));
}
}
return 0;
}
```
by hank0402 @ 2022-07-20 19:55:43
我是【】，已 AC，此帖结。
by hank0402 @ 2022-07-20 20:41:33