倍增+线性基+lca

我们可以发现线性基具有可合并性

貌似st表也是可以的

水题

#include
     
      #define re return#define ll long long #define dec(i,l,r) for(ll i=l;i>=r;--i)#define inc(i,l,r) for(ll i=l;i<=r;++i) using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=20005;int n,m,k,fa[maxn][15],deep[maxn],hd[maxn];struct node{    ll p[62];    node merge(node b)//线性基合并    {        dec(i,61,0)        {            if(p[i])            {                ll x=p[i];                dec(j,i,0)                if(x>>j)                {                    if(!b.p[j])                    {                        b.p[j]=x;                        break;                    }                    else x^=b.p[j];                }            }        }        re b;    }    inline void insert(ll x)//线性基加入    {        dec(i,61,0)        if(x>>i)        {            if(!p[i])            {                p[i]=x;                break;            }            x^=p[i];        }     }     inline void clear()    {        memset(p,0,sizeof(p));    }        inline ll Get_max()//得到最大值    {        ll sum=0;        dec(i,61,0)        if((sum^p[i])>sum)        sum^=p[i];        re sum;    }}dis[maxn][15],ans;struct ssl{    int to,nt;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}inline void dfs(int x)//dfs倍增预处理{    deep[x]=deep[fa[x][0]]+1;    for(int i=0;fa[fa[x][i]][i];++i)    {        fa[x][i+1]=fa[fa[x][i]][i];        dis[x][i+1]=dis[x][i].merge(dis[fa[x][i]][i]);    }        for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa[x][0])continue;        fa[v][0]=x;        dfs(v);    }}inline void LCA(int x,int y)//LCA求解{    ans.clear();    if(deep[x]
       
        =deep[y])    {        ans=ans.merge(dis[x][i]);        x=fa[x][i];    }    if(x==y)    {        ans=ans.merge(dis[x][0]);        re;    }        dec(i,14,0)    if(fa[x][i]!=fa[y][i])    {        ans=ans.merge(dis[x][i]);        ans=ans.merge(dis[y][i]);        x=fa[x][i];y=fa[y][i];    }    ans=ans.merge(dis[y][0]);    ans=ans.merge(dis[x][0]);    ans=ans.merge(dis[fa[x][0]][0]);    re ;}int main(){    ll x,y;        rd(n),rd(m);    inc(i,1,n)    {        rd(x);        dis[i][0].insert(x);    }        inc(i,2,n)    {        rd(x),rd(y);        add(x,y);    }    dfs(1);        inc(i,1,m)    {        rd(x),rd(y);        LCA(x,y);        printf("%lld\n",ans.Get_max());    }    re 0;}