题解 CF1363C 【Game On Leaves】
ShineEternal
2020-06-06 17:17:50
[更佳的阅读效果](https://vipblog.github.io/yPNLqcRv7/)
## description：
给定 $n$ 个节点的无根树。
两名选手轮流操作，每次可以选择一个叶节点并删除它以及所有和它相连的边。叶节点指度数不超过 $1$ 的节点。删除节点 $x$ 的选手胜利。
你需要判断先手是否有必胜策略。
## solution：
首先观察到这道题的一个特判点：如果 $x$ 刚开始就在叶子节点上，那么先手必然胜利。
注意不要忘了一个小 feature：这棵树可能只有一个节点，所以特判时不能只判度为 $1$。
那么如果不在呢？
这时我们可以知道，与 $x$ 节点相连的边数一定 $\geq 2$。所以由于两个人都实行最优策略，所以到了仅剩下两条与 $x$ 相连的边时就只会开始拆其他的点。
那么答案就只与 $n$ 的奇偶性有关了。判断一下即可。
## code：
```cpp
#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;
}
```