题目传送门：黑黑白白 (nowcoder.com)

思路 / Thought

类似巴什博奕的一个博弈题，每个分支是否“必赢”取决于它的所有儿子中是否存在“必输”，如果有一个“必输”，那么这个分支就“必赢”。对于叶子结点来说都是“必输”，因为到了这个节点就不能再往下走了。

所以这道题就是一个dfs。

代码 / Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
vector<int> g[maxn];

bool dfs(int x,int pre)//true为赢
{
    bool tag = false;//当前状态
    for(auto &i : g[x])if(i != pre)tag = tag || !dfs(i, x);
    return tag;
}

void solve()
{
    int N, R;cin >> N >> R;
    for(int i = 1;i <= N; ++ i)g[i].clear();
    for(int i = 1;i <  N; ++ i)
    {
        int x, y;cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }
    cout << (dfs(R, 0) ? "Gen" : "Dui") << '\n';
}


signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _;cin >> _;
    while(_ --)solve();
    return 0;
}