bzoj4730: Alice和Bob又在玩游戏

Description

Alice和Bob在玩游戏。有n个节点，m条边(0<=m<=n-1)，构成若干棵有根树，每棵树的根节点是该连通块内编号最
小的点。Alice和Bob轮流操作，每回合选择一个没有被删除的节点x，将x及其所有祖先全部删除，不能操作的人输
。注：树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。比如：1-3-2 这样一条链
，1号点是根节点，删除1号点之后，3号点还是2号点的父节点。问有没有先手必胜策略。n约为10w。
显然只要算出每颗子树的sg值就可以计算答案了，考虑自底向上推出sg值，用trie维护当前子树中，删去一条从根开始的链后得到的每种情况的sg值（即为与这条链相邻的子树的sg值的异或和）构成的集合，于是可以查询mex，通过trie的合并可以构建出当前点的父亲对应的集合，另外要通过打标记实现整棵trie异或上一个值。

#include<cstdio>

#include<cstring>

#include<algorithm>

const int N=;

int T,n,m;

int es[N*],enx[N*],e0[N],ed[N],ep=,f[N];

int sz[N*],ch[N*][],xt[N*],rt[N],p=;

void tag(int w,int h,int v){

    if(w&&h>=&&v){

        xt[w]^=v;

        if(v>>h&)std::swap(ch[w][],ch[w][]);

    }

}

void dn(int w,int h){

    if(xt[w]){

        tag(ch[w][],h-,xt[w]);

        tag(ch[w][],h-,xt[w]);

        xt[w]=;

    }

}

int mex(int w){

    int s=;

    for(int i=,d;~i;--i){

        dn(w,i);

        if(sz[ch[w][]]==(<<i))w=ch[w][],s|=<<i;

        else w=ch[w][];

    }

    return s;

}

int build(int x){

    int rt=++p,w;

    sz[w=rt]=;

    for(int i=;~i;--i)sz[w=ch[w][x>>i&]=++p]=;

    return rt;

}

int merge(int a,int b,int h){

    if(!a||!b)return a|b;

    dn(a,h);dn(b,h);

    ch[a][]=merge(ch[a][],ch[b][],h-);

    ch[a][]=merge(ch[a][],ch[b][],h-);

    sz[a]=h>=?sz[ch[a][]]+sz[ch[a][]]:;

    return a;

}

void dfs(int w,int pa){

    ed[w]=;

    int x=;

    for(int i=e0[w],u;i;i=enx[i]){

        u=es[i];

        if(u!=pa){

            dfs(u,w);

            x^=f[u];

        }

    }

    for(int i=e0[w],u;i;i=enx[i]){

        u=es[i];

        if(u!=pa){

            tag(rt[u],,x);

            rt[w]=merge(rt[w],rt[u],);

        }

    }

    rt[w]=merge(rt[w],build(x),);

    f[w]=mex(rt[w]);

    tag(rt[w],,f[w]);

}

int _(){

    int x=,c=getchar();

    while(c<)c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x;

}

int main(){

    for(T=_();T;--T){

        if(p){

            memset(ch,,sizeof(ch[])*(p+));

            memset(sz,,sizeof(int)*(p+));

            memset(xt,,sizeof(int)*(p+));

            p=;

        }

        n=_();m=_();

        for(int i=;i<=n;++i)e0[i]=ed[i]=f[i]=rt[i]=;

        ep=;

        for(int i=,a,b,c;i<m;++i){

            a=_();b=_();

            es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;

            es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;

        }

        for(int i=;i<=n;++i)if(!ed[i]){

            dfs(i,);

            f[]^=f[i];

        }

        puts(f[]?"Alice":"Bob");

    }

    return ;

}

bzoj4730: Alice和Bob又在玩游戏的相关教程结束。