黑黑白白(树上博弈)

描述

传送门:牛客小白月赛2-F


有一个棋子放在一颗有根树的根上。你和算卦先生轮流把这个棋子向所在点的其中一个儿子移动(只能移动到儿子)。不能再移动就算失败(即棋子所在节点没有儿子)。
算卦先生来问你,如果你先手,你是否有必胜策略?

Input

第一行一个数$T$,表示有$T$组数据。接下去每组数据的第一行有两个数$n,r$,表示树有$n$个节点,其中$r$为根节点编(从1开始编号)。
接下去$n−1$行每行两个数字$u,v$,表示点$u$和$v$之间有一条边。
$1≤T≤10$
$1≤n≤10000$
$1≤r≤n$

Output

每组数据输出一行,”Gen”表示先手有必胜策略,”Dui”表示没有。

Examples

  • intput

    1
    2
    3
    4
    5
    6
    7
    8
    9
    2
    3 1
    1 2
    2 3
    5 4
    1 2
    1 3
    3 4
    4 5
  • output

    1
    2
    Dui
    Gen

思路

  • 从叶子节点往根节点推,面对叶子节点时显然是必胜态。
  • 面对每一个节点时,如果它的子节点全都是必胜态,那么这个节点就是必败态,只要它的子节点中有一个必败态,那这个节点就是必胜态(因为可以转移成下一个人面对必败态)。
  • dfs即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e4+5;

struct node{int To,Next;}Edge[N*2]; //链式前向星存图
int cnt=0,Begin[N];

void add(int a,int b){
Edge[cnt]=(node){b,Begin[a]};
Begin[a]=cnt++;
}

bool dfs(int x,int f){ //必胜态返回true 必败返回false
for(int i=Begin[x];~i;i=Edge[i].Next){
if(Edge[i].To==f) continue;
if(!dfs(Edge[i].To,x)) return true; //如果子节点出现必败态,这个节点就是必胜态
}
return false; //子节点全是必胜态
}

int main()
{
int T,n,root,x,y;
scanf("%d",&T);
while(T--){
cnt=0;
CRL(Begin,-1);
scanf("%d%d",&n,&root);
rep(i,1,n){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
puts(dfs(root,-2)? "Gen":"Dui");
}
return 0;
}
-------------本文结束 感谢您的阅读-------------

本文标题:黑黑白白(树上博弈)

文章作者:Armin

发布时间:2019年01月11日 - 01:01

最后更新:2019年01月20日 - 12:01

原始链接:http://x-armin.com/黑黑白白/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波