前言

看到这种题直觉是树的最大匹配，如果是比赛直接打毫无疑问。
然后证明了一下也不是很难的样子。
主要是见过类似套路吧。

题意

两个人轮流给树上节点染色。
先手涂白色，后手涂黑色。
如果最后树上存在一个白色点，与其相连的没有黑点，先手胜，否则后手胜。
请你判断先手必胜还是后手必胜。

博弈

我们先给出结论：后手要赢，这颗树要有完美匹配。
首先充分性显然，有完美匹配，先手涂什么成白色，你把匹配点涂黑，那么一定任意白点都有相连黑点。
我们来证明必要性吧。
首先找到一个未匹配点，提到根，剩余可以贪心匹配。
然后你先找到一个叶子，其和父亲匹配，且父亲只有它这一个儿子，根据贪心匹配法这个父亲当然和它匹配了（和上面匹配不会更优）。
然后如果你找不到这样的叶子，说明每个叶子的父亲子树都没有完美匹配，直接就完蛋了。然后先手直接涂父亲，就直接获胜了。
否则，先手把父亲涂白，后手必须把这个叶子涂黑，否则先手直接赢了，于是完成了一轮操作，然后我们可以删去这两个点了。
显然这样步步紧逼，后手被我们强迫着动，最后根节点所有儿子一定都染成白了，然后先手再来一下，获胜。
于是我们这题只需要判断树有没有完美匹配，这个贪心即可。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100000+10;
int h[maxn],go[maxn*2],nxt[maxn*2];
int i,j,k,l,t,n,m,tot;
void add(int x,int y){
go[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
int perfect(int x,int y){
int t=h[x];
int p=0;
while (t){
if (go[t]!=y) p+=perfect(go[t],x);
t=nxt[t];
}
if (p>=2) return p;
else return p^1;
}
int main(){
scanf("%d",&n);
fo(i,1,n-1){
scanf("%d%d",&j,&k);
add(j,k);add(k,j);
}
if (perfect(1,0)==0) printf("Secondn");
else printf("Firstn");
}

最后

以上就是有魅力美女为你收集整理的[agc014d]Black and White Tree前言题意博弈的全部内容，希望文章能够帮你解决[agc014d]Black and White Tree前言题意博弈所遇到的程序开发问题。

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