1600*C. Game On Leaves（博弈游戏树）

Problem - 1363C - Codeforces

 

解析：

        我们将目标结点 x 当作树的根，显然，到当 x 的度为 1 的时候，此时行动的人胜利。

        我们假设现在的情况为，只剩余三个点，再选择任意一个点，则对方获胜。但是两个人都是聪明的，都不想在自己的行动时碰到这种情况。

        所以，我们计算当 “剩余两个点，并且其中一个点是目标点时”，总计行动了 cnt 次。

        显然，当 cnt 为偶数，则第一人获胜；否则第二人获胜。

        注意特判点数很少的情况。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,k;
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);int cnt=0;for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);if(x==k||y==k) cnt++;	//统计目标节点的度数 }if(cnt<=1) puts("Ayush");
//		else if(((n-1-cnt)+(cnt-1))%2==0) puts("Ayush"); else if((n-2)%2==0) puts("Ayush"); else puts("Ashish"); }return 0;
}