zcmimi's blog
查看原题

点击跳转

线性基搬到了树上

线性基是支持合并的

这题就是倍增暴力合并线性基

虽然O(\log^3_2n)的复杂度已经可以通过了,但是还有更优的方法

在倍增找出询问两点的lca,然后以rmq的方式合并+查询线性基,可以将复杂度降到O(\log^2_2n)

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i=x;i<=y;++i)
const int N=20011;
typedef long long ll;
int head[N],cnt,n,q,f[21][N],dep[N],l2[N];
ll a[N],d[21][N][61],ans[61];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;}
bool v[N];
void ins(ll *p,ll x){
    for(int i=60;x,~i;--i)if((x>>i)&1){
        if(!p[i]){p[i]=x;return;}
        x^=p[i];
    }
}
void mg(ll *a,ll *b){
    for(int i=60;~i;--i)
        if(a[i])ins(b,a[i]);
}
void dfs(int x){
    dep[x]=dep[f[0][x]]+1,ins(d[0][x],a[x]);
    fur(i,1,l2[dep[x]])
        f[i][x]=f[i-1][f[i-1][x]],
        mg(d[i-1][x],d[i][x]),
        mg(d[i-1][f[i-1][x]],d[i][x]);
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(to!=f[0][x])f[0][to]=x,dfs(to);
}
int lca(int x,int y){
    if(dep[x]<dep[y])x^=y,y^=x,x^=y;
    while(dep[x]>dep[y])
        x=f[l2[dep[x]-dep[y]]][x];
    if(x==y)return y;
    for(int i=l2[dep[x]];~i;--i)
        if(f[i][x]^f[i][y])
            x=f[i][x],y=f[i][y];
    return f[0][x];
}
int kth(int x,int k){
    for(int i=15;~i;--i)
        if((k>>i)&1)x=f[i][x];
    return x;
}
ll ask(int x,int y){
    memset(ans,0,sizeof ans);
    int z=lca(x,y),k=l2[dep[x]-dep[z]];
    mg(d[0][z],ans),
    mg(d[k][x],ans),
    mg(d[k][kth(x,dep[x]-dep[z]-(1<<k))],ans);
    k=l2[dep[y]-dep[z]];
    mg(d[k][y],ans),
    mg(d[k][kth(y,dep[y]-dep[z]-(1<<k))],ans);
    ll res=0;
    for(int i=60;~i;--i)
        if((res^ans[i])>res)res^=ans[i];
    return res;
}
int main(){
    scanf("%d%d",&n,&q);
    fur(i,1,n)scanf("%lld",a+i);
    int x,y;
    fur(i,2,n)
        l2[i]=l2[i>>1]+1,
        scanf("%d%d",&x,&y),
        add(x,y),add(y,x);
    dfs(1);
    while(q--)
        scanf("%d%d",&x,&y),
        printf("%lld\n",ask(x,y));
}
LG 3292 [SCOI2016]幸运数字
comment评论
Search
search