[UOJ266]Alice和Bob又在玩游戏

Tags：题解

作业部落

评论地址

---

TAG：博弈

题意

不同于树的删边游戏，删掉一个点删去的是到根的路径

题解

这题只和计算\(SG\)有关，博弈的有关内容可以移步这篇博客

这和翻棋子游戏不同！每个点不能单独考虑

考虑计算一个游戏（子树\(x\)）的\(SG\)：对其后继状态取\(mex\)

这里的后继状态是指去掉子树\(x\)内任意一个点所得的若干子游戏的异或和（联通块）

用\(SG[x]\)维护子树\(x\)游戏的\(SG\)值，考虑转移给父亲\(y\)

游戏\(y\)可以删去\(y\)结点，后继状态便是\(y\)各儿子的\(SG\)的异或和

游戏\(y\)可以删去任意\(x\)子树内的点，这时\(x\)子树内删去任意结点的后继状态会多出\(x\)的兄弟

若\(SG[x]=mex\{S\}\)，这时我们要求一个数据结构能将\(S\)中每个元素异或上一个数再合并给\(y\)的\(S_y\)

带懒标记的\(Trie\)就好了

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#define lc ch[x][0]

#define rc ch[x][1]

using namespace std;

int read()

{

	char ch=getchar();int h=0,t=1;

	while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();

	if(ch=='-') t=-1,ch=getchar();

	while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();

	return h*t;

}

const int N=4000100;

int n,m,T,ans,cnt,head[N],ch[N][2],node,siz[N];

int vis[N],SG[N],rt[N],tag[N];

struct edge{int next,to;}a[N<<1];

void link(int x,int y) {a[++cnt]=(edge){head[x],y};head[x]=cnt;}

void pushdown(int x,int d)

{

	int &s=tag[x]; if(!s) return;

	if(s&(1<<d)) swap(lc,rc);

	tag[lc]^=s;tag[rc]^=s;s=0;

}

int Merge(int x,int y,int d)

{

	if(!x||!y) return x+y;

	pushdown(x,d);pushdown(y,d);

	lc=Merge(lc,ch[y][0],d-1);

	rc=Merge(rc,ch[y][1],d-1);

	if(lc||rc) siz[x]=siz[lc]+siz[rc];

	return x;

}

void Newnode(int &x) {x=++node;lc=rc=tag[x]=0;siz[x]=1;}

void Insert(int &x,int k,int d)

{

	if(!x) Newnode(x); if(d==-1) return;

	pushdown(x,d);

	Insert(ch[x][k&(1<<d)?1:0],k,d-1);

	siz[x]=siz[lc]+siz[rc];

}

int Query(int x,int d)

{

	if(d==-1) return 0; pushdown(x,d);

	if(siz[lc]<(1<<d)) return Query(lc,d-1);

	else return Query(rc,d-1)|(1<<d);

}

void DFS(int x,int fa)

{

	vis[x]=1;int res=0;

	for(int i=head[x],R=a[i].to;i;i=a[i].next,R=a[i].to)

		if(R!=fa) DFS(R,x),res^=SG[R];

	for(int i=head[x],R=a[i].to;i;i=a[i].next,R=a[i].to)

		if(R!=fa) tag[rt[R]]^=res^SG[R],rt[x]=Merge(rt[x],rt[R],16);

	Insert(rt[x],res,16);

	SG[x]=Query(rt[x],16);

}

void work()

{

	ans=cnt=0;

	for(int i=1;i<=n;i++)

		rt[i]=vis[i]=head[i]=SG[i]=0;

	n=read();m=read();

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		link(x,y);link(y,x);

	}

	for(int i=1;i<=n;i++)

		if(!vis[i]) node=0,DFS(i,0),ans^=SG[i];

	ans?puts("Alice"):puts("Bob");

}

int main()

{

	T=read();while(T--) work();

}