这题十分的顺，应该属于能一眼瞪出来的题。
首先不定数个整数异或和最大最好办法 (也有可能是唯一办法？) 就是线性基了。然后是树上路径查询问题，基本方法有两种：1. 处理每个点到根，从问题或点的性质入手，需要挖掘性质。 2.树剖，预处理加上暴力查询，相对无脑。
可以先看看简单的树剖，其做法是对树预处理 O(\log) 条重链，每条重链维护该链预处理的信息并用线段树维护，而线性基确实支持 (\log^2) 合并，这样一来时间复杂度就是 O(q\log^2n\log^2 V ) ，其中 V 为值域。显然炸了。
那么只能选方法一，其实性质也很好挖，我们处理根到点的线性基，肯定希望线性基里留的都是深度较大的，而字典序的比较方式决定了深度大的尽量往高位送，然后代码也呼之欲出了。复杂度 O(q\log^2V)
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long;
const int N=2e4+10;
int n,q;
ll a[N];
vector<int>g[N];
int de[N],fa[N][19];
int lca(int x,int y){
if(de[x]<de[y])swap(x,y);
int c=de[x]-de[y];
for(int i=0;c;c>>=1,++i)
if(c&1)x=fa[x][i];
if(x==y)return x;
for(int i=18;~i;--i){
if(fa[x][i]==fa[y][i])continue;
x=fa[x][i],y=fa[y][i];
}return fa[x][0];
}
struct Base{
ll p[61];
int id[61];
void insert(ll x,int idx){
for(int i=60;~i;--i){
if(!(x>>i))continue;
if(!p[i]){
p[i]=x;
id[i]=idx;
break;
}
if(de[idx]>de[id[i]])
swap(x,p[i]),swap(idx,id[i]);
x^=p[i];
}
}
ll getmax(){
ll res=0;
for(int i=60;~i;--i){
if((res^p[i])>res)res^=p[i];
}return res;
}
void clear(){
memset(p,0,sizeof p);
for(int i=0;i<61;++i)id[i]=n+1;
}
}b[N],tmp;
void merge(Base f,Base h,int lim){
tmp.clear();
for(int i=0;i<61;++i){
if(de[f.id[i]]<lim)continue;
tmp.insert(f.p[i],f.id[i]);
}
for(int i=0;i<61;++i){
if(de[h.id[i]]<lim)continue;
tmp.insert(h.p[i],h.id[i]);
}
}
void dfs(int u,int fath){
fa[u][0]=fath;
de[u]=de[fath]+1;
b[u]=b[fath];
b[u].insert(a[u],u);
for(int i=1;i<19;++i)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]){
if(v==fath)continue;
dfs(v,u);
}
}
ll sol(int x,int y){
merge(b[x],b[y],de[lca(x,y)]);
return tmp.getmax();
}
int main(){
scanf("%d%d",&n,&q);
de[n+1]=n+1;
for(int i=1;i<=n;++i)scanf("%lld",&a[i]),b[i].clear();
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",sol(x,y));
}
return 0;
}