题目链接

• B - Binary Tree
  • 简单的树上博弈题，考察的是透过现象看本质、不被输入带偏的能力。
  • 首先我们知道，满k层二叉树的结点数为1+2+2²+2³+……+2^k-1^=2^k^-1
  • 注意到上面2^k-1这个数为奇数，我们还知道，任意一个数减去一个奇数都会改变其奇偶性。（奇数-奇数=偶数，偶数-奇数=奇数）
  • 最终胜利态为0（树上结点全部拿完，沦为空树），是一个偶数。
  • 如果一棵树上有奇数个结点，那么我们需要奇数次操作将其变成偶数；
  • 如果一棵树上有偶数个结点，那么我们需要偶数次操作将其变成偶数。
  • 奇数次操作，则最后一个拿到根节点的人为A；偶数次操作即为B。
  • （千万不要看到题目就去建树，这题的树是背景而不是解题模型）

代码：

#include<cstdio>
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int x,y;
		for(int i=0;i<n-1;++i)
		{
			scanf("%d%d",&x,&y);
		}
		if(n&1)
		{
			printf("Alice\n");
		}
		else
		{
			printf("Bob\n");
		}
	}
	return 0;
}