记录编号	599865	评测结果	AAAAAAAAAA
题目名称	[SCOI 2016]幸运数字	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	14.027 s
提交时间	2025-03-29 17:19:59	内存使用	170.42 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=20010,Z=62;
struct node
{
    int a[Z];
    node(){memset(a,0,sizeof(a));}
    void insert(int x)
    {
        for(int i=61;i>=0;i--) if(x&(1ll<<i))
        {
            if(a[i]==0){a[i]=x;return;}
            x^=a[i];
        }
        return;
    }
    node operator +(const node &b)const
    {
        node ls=b;
        for(int i=0;i<=61;i++) if(a[i]) ls.insert(a[i]);
        return ls;
    }
    int query()
    {
        int ls=0;
        for(int i=61;i>=0;i--) ls=max(ls,ls^a[i]);
        return ls;
    }
}s[N][17];
int n,q,l;
struct edge
{
    int ver[2*N],nxt[2*N],hd[N];
    int jsq=1;
    inline void add_edge(int x,int y)
    {
        ver[++jsq]=y;
        nxt[jsq]=hd[x];
        hd[x]=jsq;
        ver[++jsq]=x;
        nxt[jsq]=hd[y];
        hd[y]=jsq;
        return;
    }
}g;
int d[N],depth[N],f[N][17];
void dfs(int x,int fa)
{
    depth[x]=depth[fa]+1;
    f[x][0]=fa;
    s[x][0].insert(d[x]);
    s[x][0].insert(d[fa]);
    for(int i=1;i<=16;i++) f[x][i]=f[f[x][i-1]][i-1],s[x][i]=s[x][i-1]+s[f[x][i-1]][i-1];
    for(int i=g.hd[x],y;i;i=g.nxt[i])
    {
        y=g.ver[i];
        if(y==fa) continue;
        dfs(y,x);
    }
    return;
}
int getans(int a,int b)
{
    if(a==b) return d[a];
    node ans;
    if(depth[a]>depth[b]) swap(a,b);
    for(int i=16;i>=0;i--) if(depth[f[b][i]]>=depth[a])
    {
        ans=ans+s[b][i];
        b=f[b][i];
    }
    if(a==b) return ans.query();
    for(int i=16;i>=0;i--) if(f[a][i]!=f[b][i])
    {
        ans=ans+s[a][i]+s[b][i];
        a=f[a][i],b=f[b][i];
    }
    return (ans+s[a][0]+s[b][0]).query();
}
signed main()
{
    freopen("luckynum.in","r",stdin);
    freopen("luckynum.out","w",stdout);
    n=re();q=re();
    for(int i=1;i<=n;i++) d[i]=re();
    for(int i=1;i<n;i++) g.add_edge(re(),re());
    dfs(1,0);
    while(q--) printf("%lld\n",getans(re(),re()));
    return 0;
}