想法
倍增加上线性基就行惹
线性基的合并可以通过把一个线性基的元素插入到另一个里实现
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 20005
#define M 40005
ll cnt,v[N],G[N][21][62],head[N],dep[N];
ll fa[N][21],ans[62];
struct P{
int to,next;
}e[M];
void add(int x,int y){
e[++cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt;
}
void insert(ll *a,ll val){
for(int i = 61;i >= 0;--i){
if((val >> i) & 1){
if(!a[i]){
a[i] = val;
break;
}
val ^= a[i];
}
}
}
void Merge(ll *a,ll *b){
for(int i = 61;i >= 0;--i){
if(b[i])
insert(a,b[i]);
}
}
void dfs(ll u,ll f){
fa[u][0] = f;
dep[u] = dep[f] + 1;
for(int i = head[u];i;i = e[i].next){
ll v = e[i].to;
if(v == f)
continue;
dfs(v,u);
}
}
ll n,q;
void getlca(){
for(int j = 1;j <= 20;++j)
for(int i = 1;i <= n;++i){
fa[i][j] = fa[fa[i][j - 1]][j - 1];
std::memcpy(G[i][j],G[i][j - 1],sizeof(G[i][j - 1]));
Merge(G[i][j],G[fa[i][j - 1]][j - 1]);
}
}
void lca(ll x,ll y){
if(dep[x] < dep[y])
std::swap(x,y);
for(int i = 20;i >= 0;--i){
if(dep[fa[x][i]] >= dep[y]){
Merge(ans,G[x][i]);
x = fa[x][i];
}
}
if(x == y){
Merge(ans,G[x][0]);
return;
}
for(int i = 20;i >= 0;--i){
if(fa[x][i] != fa[y][i]){
Merge(ans,G[x][i]);
Merge(ans,G[y][i]);
x = fa[x][i];
y = fa[y][i];
}
}
Merge(ans,G[x][0]),Merge(ans,G[y][0]),Merge(ans,G[fa[x][0]][0]);
return;
}
inline ll read(){
ll ans = 0,f = 1;
char a = getchar();
while(a < '0' && a > '9' && (a != '-'))
a = getchar();
if(a == '-')
f = -1,a = getchar();
while(a <= '9' && a >= '0'){
ans = (ans << 3) + (ans << 1) + (a - '0'),a = getchar();
}
return ans * f;
}
int main(){
n = read(),q = read();
for(int i = 1;i <= n;++i)
insert(G[i][0],read());
for(int i = 1;i <= n - 1;++i){
ll x = read(),y = read();
add(x,y);
add(y,x);
}
dfs(1,0);
getlca();
for(int i = 1;i <= q;++i){
ll u = read(),v = read();
std::memset(ans,0,sizeof(ans));
lca(u,v);
ll sum = 0;
for(int i = 61;i >= 0;--i){
if(ans[i])
sum = std::max(sum,sum ^ (ans[i]));
}
std::cout<<sum<<std::endl;
}
}