想不到还有线性基合并这种骚操,知道这个骚操之后。

打了一发$O(mlog^4n)$的树剖,$T$得飞起。

无奈打倍增,$O(mlog^2n)$的,由于线性基是可以类似RMQ合并的,所以不是$log^3n$的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e4+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    ll a[61];
    node(ll x=0ll)
    {
        memset(a,0,sizeof(a));
        for(int i=60;~i;i--)
            if(x>>i&1){a[i]=x;return ;}
    }
    node operator +(const node w)const
    {
        node p;ll b[122];int l=0;
        for(int i=60;~i;i--)if(a[i])b[++l]=a[i];
        for(int i=60;~i;i--)if(w.a[i])b[++l]=w.a[i];
        for(int i=1;i<=l;i++)
            for(int j=60;~j;j--)
                if(b[i]>>j&1)
                {
                    if(p.a[j])b[i]^=p.a[j];
                    else {p.a[j]=b[i];break;}
                    if(!b[i])break;
                }
        return p;
    }
}d[N][16];
int fa[N][16],dep[N],Log[N];ll A[N];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;~i;i--)
        if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=15;~i;i--)
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs(int x)
{
    for(int i=1;i<=Log[dep[x]];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1],
        d[x][i]=d[x][i-1]+d[fa[x][i-1]][i-1];
    for(int k=last[x],y;k;k=a[k].next)
    {
        if((y=a[k].y)==fa[x][0])continue;
        fa[y][0]=x;dep[y]=dep[x]+1;d[y][0]=node(A[y]);
        dfs(y);
    }
}
int kth(int x,int k)
{
    for(int i=15;~i;i--)
        if(k>=(1<<i))x=fa[x][i],k-=1<<i;
    return x;
}
void query(int x,int y)
{
    int f=lca(x,y),l=Log[dep[x]-dep[f]];
    node now=node(0ll);
    now=(now+d[x][l])+d[kth(x,dep[x]-dep[f]-(1<<l))][l];
    l=Log[dep[y]-dep[f]];
    now=(now+d[y][l])+d[kth(y,dep[y]-dep[f]-(1<<l))][l];
    now=now+d[f][0];ll ans=0;
    for(int i=60;~i;i--)
        if((ans^now.a[i])>ans)ans^=now.a[i];
    qw(ans);puts("");
}
int main()
{
    int n,q;qr(n),qr(q);
    for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;i++)qr(A[i]);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    d[1][0]=node(A[1]);fa[1][0]=0;dfs(1);
    for(int i=1;i<=q;i++)
    {
        int x,y;qr(x),qr(y);
        query(x,y);
    }
    return 0;
}