C++14(g++5.4) 解法, 执行用时: 41ms, 内存消耗: 1700K, 提交时间: 2020-09-26 15:18:39

#include<iostream>
#include<vector> 
using namespace std;
vector<int>mp[10001];
int t,n,r,u,v;
bool dfs(int x,int f){
	int len=mp[x].size();//当前节点的分支个数 
	for(int i=0;i<len;i++){
		int xx=mp[x][i];//当前节点的分支节点 
		if(xx!=f && !dfs(xx,x)){// xx!=f不可以是环 ，判断xx节点的分支节点，同时保证了奇数为true 
			return true;
		}
	}
	return false;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>r;
		for(int i=0;i<=n;i++){
			mp[i].clear();
		}
		for(int i=1;i<n;i++){
			cin>>u>>v;
			mp[u].push_back(v);
			mp[v].push_back(u);
		}
		cout<<(dfs(r,-1)?"Gen\n":"Dui\n");//从根节点出发 
	}
	return 0;
} 

Python3(3.5.2) 解法, 执行用时: 507ms, 内存消耗: 8768K, 提交时间: 2018-11-11 11:25:07

import sys
sys.setrecursionlimit(10**6)
T = int(input())
def dfs(u, p, e, a):
    for v in e[u]:
        if v != p:
            dfs(v, u, e, a)
            if a[v]:
                a[u] = False
                return
    a[u] = True
while T > 0 :
    T -= 1
    n, r = map(int, input().split())
    e = [[] for i in range(n)]
    a = [False] * n
    for i in range(n - 1):
        u, v = map(int, input().split())
        e[u - 1].append(v - 1)
        e[v - 1].append(u - 1)
    dfs(r - 1, -1, e, a)
    print('Gen' if not a[r - 1] else 'Dui')

C++11(clang++ 3.9) 解法, 执行用时: 70ms, 内存消耗: 1796K, 提交时间: 2020-01-28 17:03:39

#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
vector<int>vv[10005];
int dfs(int x,int f){
	for(int t:vv[x]) if(t!=f&&!dfs(t,x)) return 1;
	return 0;
}
int main(){
	int _; cin>>_; while(_--){
		int n,r; cin>>n>>r;
		rep(i,1,n+1) vv[i].clear();
		rep(i,1,n){
			int u,v; cin>>u>>v;
			vv[u].push_back(v);
			vv[v].push_back(u);
		} puts(dfs(r,0)?"Gen":"Dui");
	}
}