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=100007; int T,n,m; int es[N*2],enx[N*2],e0[N],ed[N],ep=2,f[N]; int sz[N*40],ch[N*40][2],xt[N*40],rt[N],p=0; void tag(int w,int h,int v){ if(w&&h>=0&&v){ xt[w]^=v; if(v>>h&1)std::swap(ch[w][0],ch[w][1]); } } void dn(int w,int h){ if(xt[w]){ tag(ch[w][0],h-1,xt[w]); tag(ch[w][1],h-1,xt[w]); xt[w]=0; } } int mex(int w){ int s=0; for(int i=19,d;~i;--i){ dn(w,i); if(sz[ch[w][0]]==(1<<i))w=ch[w][1],s|=1<<i; else w=ch[w][0]; } return s; } int build(int x){ int rt=++p,w; sz[w=rt]=1; for(int i=19;~i;--i)sz[w=ch[w][x>>i&1]=++p]=1; return rt; } int merge(int a,int b,int h){ if(!a||!b)return a|b; dn(a,h);dn(b,h); ch[a][0]=merge(ch[a][0],ch[b][0],h-1); ch[a][1]=merge(ch[a][1],ch[b][1],h-1); sz[a]=h>=0?sz[ch[a][0]]+sz[ch[a][1]]:1; return a; } void dfs(int w,int pa){ ed[w]=1; int x=0; 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],19,x); rt[w]=merge(rt[w],rt[u],19); } } rt[w]=merge(rt[w],build(x),19); f[w]=mex(rt[w]); tag(rt[w],19,f[w]); } int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x; } int main(){ for(T=_();T;--T){ if(p){ memset(ch,0,sizeof(ch[0])*(p+1)); memset(sz,0,sizeof(int)*(p+1)); memset(xt,0,sizeof(int)*(p+1)); p=0; } n=_();m=_(); for(int i=0;i<=n;++i)e0[i]=ed[i]=f[i]=rt[i]=0; ep=2; for(int i=0,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=1;i<=n;++i)if(!ed[i]){ dfs(i,0); f[0]^=f[i]; } puts(f[0]?"Alice":"Bob"); } return 0; }