[AGC014D] Black and White Tree（树形DP，博弈）

每次找到所有叶子节点，把它们的父亲染白，自己染黑。这个时候染完的叶子节点及其父亲节点对树的其他部分已无影响 ,可以直接删掉。

那么只需要判断树的其他部分是否有先手必胜策略即可。用递归遍历。

边界条件：若树为单一节点先手必胜。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
struct Edge{
int v,nxt;
}e[N<<1];
int n,flag[N],cnt,head[N];
void add(int x,int y){
e[++cnt].v=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
bool dfs(int x,int fa){
flag[x]=1;
int tot=0;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
if(dfs(v,x)) return true;
if(flag[v]){
tot++;flag[x]=0;
if(tot==2)return true;
}
}
return false;
}
int main(){
scanf("%d",&n);
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
printf(dfs(1,0)||flag[1]?"First":"Second");
return 0;
}

最后

以上就是开心睫毛为你收集整理的[AGC014D] Black and White Tree（树形DP，博弈）的全部内容，希望文章能够帮你解决[AGC014D] Black and White Tree（树形DP，博弈）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。