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

发布时间:2024年01月08日

题目链接: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 ;
}

文章来源:https://blog.csdn.net/weixin_50089904/article/details/135428476
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。