Codeforces Round 646 (Div. 2) C. Game On Leaves

题目链接：Problem - 1363C - Codeforces

题意：给定一颗树和一个节点x，每次从这棵树上删除一个叶子节点及其任何一条连接的边，Ayush先手，问谁先取到节点x。

博弈论问题，先看两个样例是如何取到的。

对于样例一，不管Ayush先选择去掉哪一个节点，节点x都会被Ashish拿走。

对于样例二，Ayush可以直接拿走节点x。

我们可以得出对于Ayush如果节点x本来就是叶子节点，那他就可以直接取走

再观察以下两种情况：

Ayush可以先取节点4，然后将必败态留给Ashish，一定胜利。

而对于这个样例，Ayush不管选择5还是3都会把必胜态留给Ashish，一定失败。

不难发现，当节点x相连的节点及其子节点有奇数个时，Ayush胜利，反之，Ashish胜利。

则Ayush胜利有两种情况：

1.节点x的节点及其子节点有奇数个。

2.节点x为叶子节点。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1010 ;
int n , x , res , s ;
int h[N] , e[N * 2] , ne[N * 2] , idx ;

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int fa)
{
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i] ;
        if(j == fa) continue ;
        res ++ ;
        if(u == x) s ++ ;
        dfs(j , u) ;
    }
}
void solve()
{
    cin >> n >> x ;
    memset(h , -1 , sizeof h) ;
    idx = 0 ;
    for(int i = 1 ; i < n ; i ++)
    {  
        int a , b ;
        scanf("%lld%lld",&a,&b) ;
        add(a , b) , add(b , a) ;
    }
    res = 0 , s = 0 ;
    dfs(x , -1) ;
    if(res % 2 || s <= 1) puts("Ayush") ;
    else puts("Ashish") ;
}

signed main()
{
    int t ;
    cin >> t ;
    while(t --)
    {
        solve() ;
    }
    return 0 ;
}