@ysner
2018-07-31T00:21:01.000000Z
字数 1242
阅读 1857
博弈论
一棵个点的有根树,两个人轮流操作。一次操作是选择一条边,删除此边以及删掉边后和根不连通的部分。询问谁有必胜策略。
可以把这棵树看成一堆石子,每个点(或它的父边)看成一个石子。
这就很像游戏了。
有个结论。
原来想把子树根结点各儿子的值和根单独的值求个异或和,来得到该子树的值。
后来发现自己似乎不知道根单独的值。。。
所以应把子树根结点各儿子的值加,把它们包括的情况延伸到子树根节点,再进行异或,才能得到整个子树的值。
根节点的值就是整个游戏的值。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
struct Edge{int to,nxt;}e[N<<1];
int n,m,h[N],cnt;
ll ans;
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int dfs(re int u,re int fa)
{
re int SG=0;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
SG^=(dfs(v,u)+1);
}
return SG;
}
int main()
{
ios::sync_with_stdio(false);
re int T=gi();
while(T--)
{
n=gi();cnt=0;memset(h,-1,sizeof(h));
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);add(v,u);
}
puts(dfs(1,0)?"Alice":"Bob");
}
return 0;
}