题解 | #黑黑白白#

感觉和上一题考察点有一些重复，都是最基础的博弈论。

解决这题我们需要知道下面的两点：

• 如果我走了一步，对方处于“必败”境地，那么我就处于“必胜”境地。
• 如果我的所有下一步状态都是“必败”态，那么我就会输，只要有一个“必胜”的我走那一条路就可以。

所以既然它就是个树形结构，直接遍历这棵树，把所有孩子结点的答案向上合并即可！

#include<cstdio>
#include<vector>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e4 + 5;
std::vector<int>G[N];
bool dfs(int u, int fa) {
    bool tp = 0;
    for (std::vector<int>::iterator it = G[u].begin(); it != G[u].end(); ++it) {
        int v = *it;
        if (v == fa) continue;
        if (!dfs(v, u))
            tp = 1;
    }
    return tp;
}
int main(){
    int T = init();
    while (T--) {
        int n = init(), r = init();
        for (int i = 1; i <= n; ++i)
            G[i].clear();
        for (int i = 1; i < n; ++i) {
            int u = init(), v = init();
            G[u].push_back(v), G[v].push_back(u);
        }
        puts(dfs(r, r) ? "Gen" : "Dui");
    }
}