题解 P3292 【[SCOI2016]幸运数字】

· · 题解

我的博客，欢迎来踩( • ̀ω•́ )✧

提供一个两个log的在线做法，有点类似kcz说的序列做法
kcz说的那个，可以去做这题，裸的

对每一个点，我们可以预处理出从根到它的线性基，并且贪心的让高位的向量对应的点深度尽量大，并预处理出 pos[x][i] 表示 x 号结点第 i 位的向量对应最深的点，可以用以下代码求出。

LL bas[N][61];
int pos[N][61];
void ins(int p,LL bas[],int pos[]){
    LL x=a[p];
    if (x==0) return;
    rf(i,60,0)
     if ((x>>i)&1){
        if (!bas[i]){
            bas[i]=x;pos[i]=p;
            break;
        }
        if (dep[p]>dep[pos[i]]) swap(pos[i],p),swap(x,bas[i]); //确保第i位深度尽量大
        x^=bas[i];
     }
}

这样写正确性是显然的，当第 i 位碰到了一个更深的点的时候，就相当于交换了一下插入的顺序。

然后对于一个查询 x,y ，假设其LCA深度为 d ，我们只取 pos[x][i] \geq d 和 pos[y][i] \geq d 的那些向量，暴力合并就行了ヾ(◍°∇°◍)ﾉﾞ

这个算法跑得很快，我也没特意卡常，就洛谷第二页（开O2就rank2）了，BZOJ是rank5。
作为kcz的小迷妹，在此悄悄%%%kcz

最后贴一下丑陋的代码，感觉比点分什么的好写啊~

#include<bits/stdc++.h>
#define LL long long
#define re register
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
#define frz(i,x,y) for(int i=x,z=y;i<=z;i++)
using namespace std;
const int N=20002;
const int M=N<<1;
const int Lg=15;
int n,q;
LL a[N];
int cnt,head[N],Next[M],v[M];

inline void read(int &x){
    char ch=getchar();x=0;int w=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    if (w) x=-x;
}
inline void read(LL &x){
    char ch=getchar();x=0;int w=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    if (w) x=-x;
}

void add(int x,int y){ Next[++cnt]=head[x];head[x]=cnt;v[cnt]=y; }

int dep[N],f[N][Lg];
LL bas[N][61];
int pos[N][61];
void ins(int p,LL bas[],int pos[]){
    LL x=a[p];
    if (x==0) return;
    rf(i,60,0)
     if ((x>>i)&1){
        if (!bas[i]){
            bas[i]=x;pos[i]=p;
            break;
        }
        if (dep[p]>dep[pos[i]]) swap(pos[i],p),swap(x,bas[i]);
        x^=bas[i];
     }
}

void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    frl(i,1,Lg) f[x][i]=f[f[x][i-1]][i-1];

    fr(i,0,60) pos[x][i]=pos[fa][i],bas[x][i]=bas[fa][i];
    ins(x,bas[x],pos[x]);

    for(int i=head[x];i;i=Next[i])
     if (v[i]!=fa) dfs(v[i],x);
}

int getLCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    rf(i,Lg-1,0) if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    rf(i,Lg-1,0) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

LL base[61];
int main(){
    read(n);read(q);
    fr(i,1,n) read(a[i]);
    int x,y;
    fr(i,2,n){
        read(x);read(y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    while(q--){
        read(x);read(y);
        int lca=getLCA(x,y);
        rf(i,60,0) if (dep[pos[x][i]]>=dep[lca]) base[i]=bas[x][i];else base[i]=0;
        rf(i,60,0)
         if (dep[pos[y][i]]>=dep[lca]){
            LL x=bas[y][i];
            if (x==0) continue;
            rf(j,i,0)
             if ((x>>j)&1){
                if (!base[j]){ base[j]=x;break; }
                x^=base[j];
             }
         }
        LL ans=0;
        rf(i,60,0) if ((ans^base[i])>ans) ans^=base[i];
        printf("%lld\n",ans);
    }
    return 0;
}