洛谷 P3292 【SCOI2016】幸运数字/BZOJ 4568 幸运数字 题解

洛谷 P3292 【SCOI2016】幸运数字/BZOJ 4568 幸运数字 题解

2020-2-12 xiaoh

题意

给一张含有$n$个节点的树($1\leq n \leq 2\times 10^4$)，第$i$个节点上有$1$个数$a_i(1\leq a_i \leq 2^{60})$。接下来有$q$个询问($1\leq q \leq 2\times 10^5$)，每个询问给定两个点$u,v$，求两点间路径上包含的点的子集的最大异或和。

题解

看到子集异或和，一下子想到线性基。又因为要维护树链上的信息，所以自然想到了树链剖分万能的LCA。于是乎我们考虑用LCA的倍增来维护线性基就可以通过啦！时间复杂度$O(nw^2logn+mw^2)$,空间复杂度$O(nwlogn)$,虽然复杂度一路狂飙直上$10^9$，然鹅我们可以看一看数据：洛谷是$2s$~$6s$,BZOJ是$60s$，随便在线性基上加几个$register$卡卡常就能轻松飘过去。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return;
}
template<typename T>
inline void write(T x)
{
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=20010,LOGN=15,W=61;
class LinearBasis{//封装后的线性基板子
public:
    long long a[W+1];
    inline void init()//初始化
    {
        memset(a,0,sizeof(a));
    }
    inline void insert(long long x)//插入
    {
        for(register int i=W;i>=0;i--)
        {
            if(!x) return;
            if(!((x>>i)&1ll)) continue;
            if(a[i]) x^=a[i];
            else
            {
                for(register int j=0;j<i;j++)
                if((x>>j)&1ll) x^=a[j];
                for(register int j=i+1;j<=W;j++)
                if((a[j]>>i)&1ll) a[j]^=x;
                a[i]=x;
                return;
            }
        }
    }
    inline void merge(LinearBasis x)//合并两个线性基
    {
        for(register int i=0;i<=W;i++) insert(x.a[i]);
    }
    inline long long query()//查询子集xor和
    {
        long long ret=0;
        for(register int i=0;i<=W;i++) ret^=a[i];
        return ret;
    }
}f[MAXN][LOGN+1];
int n,m;
long long a[MAXN];
int tot=1;
int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
inline void add_edge(int u,int v)//链式前向星
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
bool book[MAXN];
queue<int> q;
int LCA[MAXN][LOGN+1],d[MAXN];
inline void prework()//LCA预处理
{
    d[1]=1,book[1]=1,q.push(1);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(register int i=hd[x];i;i=nxt[i])
        {
            int y=edge[i];
            if(book[y]) continue;
            LCA[y][0]=x,f[y][0].insert(a[x]);
            d[y]=d[x]+1;
            book[y]=1,q.push(y);
            for(int j=1;j<=LOGN;j++)
            LCA[y][j]=LCA[LCA[y][j-1]][j-1],
            f[y][j].merge(f[y][j-1]),f[y][j].merge(f[LCA[y][j-1]][j-1]);
        }
    }
}
inline long long query(int x,int y)//倍增查询
{
    LinearBasis ans;
    ans.init();
    ans.insert(a[x]),ans.insert(a[y]);
    if(d[x]<d[y]) swap(x,y);
    for(int i=LOGN;i>=0;i--)
    if(d[LCA[x][i]]>=d[y]) ans.merge(f[x][i]),x=LCA[x][i];
    if(x==y) return ans.query();
    for(int i=LOGN;i>=0;i--)
    if(LCA[x][i]!=LCA[y][i])
    ans.merge(f[x][i]),ans.merge(f[y][i]),x=LCA[x][i],y=LCA[y][i];
    ans.merge(f[x][0]);
    return ans.query();
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u),read(v);
        add_edge(u,v),add_edge(v,u);
    }
    prework();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u),read(v);
        write(query(u,v)),putchar('\n');
    }
}