HarmoniikaaHarmoniikaa BZOJ 4568

#define ll long long
#define N 20010
using namespace std;
 
struct {
  ll b[62];
  int siz;
     
  XXJ(){
    siz=0;
    memset(b,0,sizeof(b));
  }
     
  void insert(ll x){
    for(ll i=60;i>=0;i--){
      if(x&(1ll<<i)){
	if(b[i]==0){
	  b[i]=x;
	  siz++;
	  break;
	}
	x^=b[i];
      }
    }
  }
     
  ll getmax(){
    ll ret=0;
    for(ll i=60;i>=0;i--){
      if((ret^b[i])>ret){
	ret=ret^b[i];
      }
    }
    return ret;
  }
};
 
struct Node{
  XXJ g;
  int l,r;
}t[N<<2];
 
struct Edge{
  int to,next;
}e[N<<1];
 
int ne,n,q,head[N];
int son[N],siz[N],dep[N],dad[N];
int top[N],w[N],pos[N],tot;
ll v[N];
 
void ins(int u,int v){
  ne++;
  e[ne].to=v;
  e[ne].next=head[u];
  head[u]=ne;
}
 
void insert(int u,int v){
  ins(u,v);ins(v,u);
}
 
XXJ merge(XXJ A,XXJ B){
  if(A.siz>B.siz) swap(A,B);
  if(B.siz==60) return B;
  for(int i=60;i>=0;i--){
    if(A.b[i]){
      B.insert(A.b[i]);
    }
  }
  return B;
}
 
void dfs1(int x,int fa){
  siz[x]=1;dep[x]=dep[fa]+1;dad[x]=fa;
  for(int i=head[x];i;i=e[i].next){
    int v=e[i].to;
    if(v==dad[x]) continue;
    dfs1(v,x);
    siz[x]+=siz[v];
    if(siz[v]>siz[son[x]]) son[x]=v;
  }
}
 
void dfs2(int x,int chain){
  top[x]=chain;w[x]=++tot;pos[tot]=x;
  if(son[x]) dfs2(son[x],chain);
  for(int i=head[x];i;i=e[i].next){
    int v=e[i].to;
    if(v==dad[x]||v==son[x]) continue;
    dfs2(v,v);
  }
}
 
void pushup(int rt){
  t[rt].g=merge(t[rt<<1].g,t[rt<<1|1].g);
}
 
void build(int rt,int l,int r){
  t[rt].l=l;t[rt].r=r;
  if(l==r){
    t[rt].g.insert(v[pos[l]]);
    return;
  }
  int mid=(l+r)>>1;
  build(rt<<1,l,mid);
  build(rt<<1|1,mid+1,r);
  pushup(rt);
}
 
XXJ query(int rt,int l,int r){
  if(l<=t[rt].l&&t[rt].r<=r){
    return t[rt].g;
  }
  int mid=(t[rt].l+t[rt].r)>>1;
  if(l<=mid&&mid<r){
    return merge(query(rt<<1,l,r),query(rt<<1|1,l,r));
  }
  if(l<=mid) return query(rt<<1,l,r);
  if(mid<r) return query(rt<<1|1,l,r);
}
 
ll find(int x,int y){
  XXJ ret;
  for(;top[x]!=top[y];x=dad[top[x]]){
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    ret=merge(ret,query(1,w[top[x]],w[x]));
  }
  if(dep[x]<dep[y]) swap(x,y);
  ret=merge(ret,query(1,w[y],w[x]));
  return ret.getmax();
}
 
int main(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
  for(int i=1;i<n;i++){
    int u,v;
    scanf("%d%d",&u,&v);
    insert(u,v);
  }
  dfs1(1,0);
  dfs2(1,1);
  build(1,1,n);
  while(q--){
    int u,v;
    scanf("%d%d",&u,&v);
    printf("%lldn",find(u,v));
  }
  return 0;
}