```
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int mxn=2e4+5;
int n,q;
long long val[mxn],ans[64],dep[mxn],f[mxn][20],p[mxn][20][64];
vector<int > g[mxn];
inline void ins(long long *s,long long x)
{
for(int i=63;i>=0;--i) {
if(x>>i==0) continue;
if(!s[i]) {s[i]=x;break;}
x^=s[i];
}
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for(int i=0;i<g[u].size();++i) {
int v=g[u][i];
if(v==fa) continue ;
dfs(v,u);
f[v][0]=u;
}
}
inline void print()
{
long long tp=0;
for(int i=63;i>=0;--i)
if((ans[i]^tp)>tp) tp^=ans[i];
printf("%lld\n",tp);
}
void init()
{
for(int j=1;j<=18;++j)
for(int i=1;i<=n;++i) {
f[i][j]=f[f[i][j-1]][j-1];
for(int k=63;k>=0;--k)
p[i][j][k]=p[i][j-1][k];
for(int k=63;k>=0;--k)
if (p[f[i][j-1]][j-1][k])
ins(p[i][j],p[f[i][j-1]][j-1][k]);
// for(int k=0;k<=63;++k) ans[i]=p[i][j][k];
// cout<<i<<" "<<j<<endl;
// print();
}
}
void solve(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=18;i>=0;--i)
if(dep[f[x][i]]>=dep[y]) {
for(int k=63;k>=0;--k)
ins(ans,p[x][i][k]);
x=f[x][i];
}
if(x==y) {
for(int k=63;k>=0;--k)
ins(ans,p[x][0][k]);
print();
memset(ans,0ll,sizeof(ans));
return ;
}
for(int i=18;i>=0;--i)
if(f[x][i]!=f[y][i]) {
x=f[x][i],y=f[y][i];
for(int k=63;k>=0;--k)
ins(ans,p[x][i][k]),ins(ans,p[y][i][k]);
}
for(int i=63;i>=0;--i)
ins(ans,p[x][0][i]),ins(ans,p[y][0][i]),ins(ans,p[f[x][0]][0][i]);
print();
memset(ans,0,sizeof(ans));
}
int main()
{
int u,v;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;++i) {
scanf("%lld",&val[i]);
ins(p[i][0], val[i]);
}
for(int i=1;i<n;++i) {
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,1);init();
for(int i=1;i<=q;++i) {
scanf("%d %d",&u,&v);
solve(u,v);
}
return 0;
}
```
by cloud_9 @ 2018-12-30 20:30:16
大佬太强了看不懂阿!
by qrsikno @ 2018-12-30 20:44:07