首页 > 代码库 > 【HDU3094】A tree game 博弈,树形删边游戏

【HDU3094】A tree game 博弈,树形删边游戏

转载请注明出处:http://blog.csdn.net/vmurder/article/details/42653129

其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。


题意:给一颗树,每次可以删掉一条与节点1(root)的连通的边,两人轮流操作,谁不能操作谁输。

题解:

只能套公式:

Colon原理:SG(x)=XOR{SG(y)+1|y是x的子结点}。


好了。水了。


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
using namespace std;
struct KSD
{
	int v,next;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int n;
int sg[N];
void dfs(int x,int p)
{
	int i,v;
	sg[x]=0;
	for(i=head[x];i;i=e[i].next)
	{
		v=e[i].v;
		if(v==p)continue;
		dfs(v,x);
		sg[x]^=(sg[v]+1);
	}
}
int main()
{
	int i,j,T;
	int a,b;
	for(scanf("%d",&T);T--;)
	{
		cnt=1;
		memset(head,0,sizeof(head));
		scanf("%d",&n);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			add(a,b),add(b,a);
		}
		dfs(1,0);
		if(sg[1])puts("Alice");
		else puts("Bob");
	}
	return 0;
}


【HDU3094】A tree game 博弈,树形删边游戏