\(\text{Solution:}\)
这题是个板子。显然的思路就是直接用树剖线段树维护合并线性基，这样就可以做到 \(O(n\log ^4 n)\) 的复杂度。
这东西 十分卡常 ，所以代码里用了 fread,fwrite 等优化，以及：
合并线性基的时候，我们会发现，一个位置只会往比它低的位置合并。
加上这个优化就可以直接快一半。
于是靠着这个优化就直接草过去了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll Max(ll x,ll y){return x>y?x:y;}
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
ll s=0;
char ch=getchar();
while(!isdigit(ch)){ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s;
}
char obuf[1<<23],*O=obuf;
inline void write(ll x){
if(x>9)write(x/10);
*O++=x%10+'0';
}
const int N=1e5+10;
namespace Refined_heart{
int n,q,son[N],dep[N],pa[N];
int top[N],rk[N],id[N],dfstime;
int head[N],tot,rt,siz[N];
ll val[N];
struct E{int nxt,to;}e[N];
inline void link(int x,int y){
e[++tot]=(E){head[x],y};
head[x]=tot;
}
struct Base{
ll p[61];
Base(){memset(p,0,sizeof p);}
void insert(ll x){
if(!x)return;
for(int i=60;~i&&x;--i){
if(!(x>>i&1))continue;
if(p[i])x^=p[i];
else{p[i]=x;return;}
}
return;
}
};
Base merge(Base A,Base B){
for(int i=60;~i;--i){
ll t=B.p[i];
if(!t)continue;
for(int j=i;~j&&t;--j){
if(!(t>>j&1))continue;
if(!A.p[j]){
A.p[j]=t;
break;
}
t^=A.p[j];
}
}
return A;
}
struct SGT{
int ls[N],rs[N],node;
Base f[N];
inline void pushup(int x){f[x]=merge(f[ls[x]],f[rs[x]]);}
void build(int &x,int l,int r){
x=++node;
if(l==r){
f[x].insert(val[rk[l]]);
return;
}
int mid=(l+r)>>1;
build(ls[x],l,mid);
build(rs[x],mid+1,r);
pushup(x);
}
Base query(int x,int L,int R,int l,int r){
if(L>=l&&R<=r)return f[x];
int mid=(L+R)>>1;
Base ans;
if(l<=mid)ans=merge(ans,query(ls[x],L,mid,l,r));
if(mid<r)ans=merge(ans,query(rs[x],mid+1,R,l,r));
return ans;
}
}tr;
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;
siz[x]=1;pa[x]=fa;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==fa)continue;
dfs1(j,x);
siz[x]+=siz[j];
if(siz[j]>siz[son[x]])son[x]=j;
}
}
void dfs2(int u,int t){
top[u]=t;
rk[id[u]=++dfstime]=u;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int j=e[i].to;
if(j==son[u]||j==pa[u])continue;
dfs2(j,j);
}
}
Base Ans;
void chain(int x,int y){
memset(Ans.p,0,sizeof Ans.p);
for(;top[x]!=top[y];){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Ans=merge(Ans,tr.query(rt,1,n,id[top[x]],id[x]));
x=pa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
Ans=merge(Ans,tr.query(rt,1,n,id[x],id[y]));
ll A=0;
for(int i=60;~i;--i)A=Max(A,A^Ans.p[i]);
write(A);*O++='\n';
}
void solve(){
n=read();q=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
link(u,v);link(v,u);
}
dfs1(1,0);dfs2(1,1);
tr.build(rt,1,n);
for(int i=1,x,y;i<=q;++i){
x=read(),y=read();
chain(x,y);
}
fwrite(obuf,1,O-obuf,stdout);
}
}
signed main(){
freopen("in.txt","r",stdin);
freopen("My.out","w",stdout);
Refined_heart::solve();
return 0;
}