CF1363C Game On Leaves 题解

description：

给定 $n$ 个节点的无根树。

两名选手轮流操作，每次可以选择一个叶节点并删除它以及所有和它相连的边。叶节点指度数不超过 $1$ 的节点。删除节点 $x$ 的选手胜利。

你需要判断先手是否有必胜策略。

solution：

首先观察到这道题的一个特判点：如果 $x$ 刚开始就在叶子节点上，那么先手必然胜利。

注意不要忘了一个小 feature：这棵树可能只有一个节点，所以特判时不能只判度为 $1$。

那么如果不在呢？

这时我们可以知道，与 $x$ 节点相连的边数一定 $\geq 2$。所以由于两个人都实行最优策略，所以到了仅剩下两条与 $x$ 相连的边时就只会开始拆其他的点。

那么答案就只与 $n$ 的奇偶性有关了。判断一下即可。

code：

#include<cstdio>
#include<cstring>
using namespace std;
int p[1005];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int a,b;
		int n,x;
		scanf("%d%d",&n,&x);
		memset(p,0,sizeof(p));
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			p[a]++;
			p[b]++;
		}
		if(p[x]<=1)
		{
			printf("Ayush\n");
		}
		else
		{
			if(n%2==1)
			{
				printf("Ashish\n");
			}
			else
			{
				printf("Ayush\n");
			}
		}
	}
	return 0;
}