树上删边游戏
参考链接:https://wenku.baidu.com/view/6e1395f78aeb172ded630b1c59eef8c75fbf953b.html
如果是一堆竹子的话,很明显跟取石子Nim游戏一样
克朗原理:对于树上某一个点,它的分支可以转换为以这个点为根的一根竹子,这个竹
子的长度等于它各个分支的边的数量的异或和。
(When branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum.)
对于该图,1号点有2个分支,分支上的边树分别为1、1,异或和为0,所以1号点的分支被替换为长度为0的竹子,也就是说上面两个分支被删掉了。所以对于2号点,就剩下2个分支,同理被消掉。最后这个图被转化为一根长度为1的竹子,其SG值为1。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef pair<int,int> pii;
typedef long long ll;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif
const int N =100005,M=2*N;
int h[N],e[M],ne[M],idx;
void add(int x,int y)
{
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
int dfs(int u,int fa)//返回(所有孩子+1)的异或和
{
int res=0;
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
res^=dfs(v,u)+1;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
memset(h,-1,sizeof (int)*(n+3));
idx=0;
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
int res=dfs(1,-1);
puts(res==0?"Bob":"Alice");
}
}
如果扩展成图上删边游戏
费森原理:环上的点可以在被融合,且不改变图的SG值。
一般来说,我们可以把一个带有奇数边的环等价于只有一个端点的一条边,而偶数边的环等价于一个点。