[SCOI2016]幸运数字

洛谷

倍增+线性基+lca

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

貌似st表也是可以的

水题

#include<bits/stdc++.h>
#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<typename T>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])x^=y^=x^=y;
    
    dec(i,14,0)
    if(deep[fa[x][i]]>=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
",ans.Get_max());
    }
    re 0;
}