[agc014d] Black and White Tree（玄学树D）

Description

有一颗n个点的树，刚开始每个点都没有颜色。

Alice和Bob会轮流对这棵树的一个点涂色，Alice涂白，Bob涂黑，Alice先手。

若最后存在一个白点，使得这个白点所有相邻点都为白色，则Alice胜，否则Bob胜。

请问是先手必胜还是后手必胜。

Input

第一行一个整数n。

接下来n-1行每行两个整数ai,bi，表示有一条边连接ai,bi。

Output

若先手必胜，输出"First"（不含引号），否则输出"Second"（不含引号）。

题解：

首先想到如果有一个点的儿子中包含两个或以上个叶子结点，先手必胜，否则先手必败。

发现这样不行，其实先手可以牵制对手，选一个叶子结点的父亲，那么后手就必须下在这个叶子结点上。

这相当于把这两个节点都删掉了，从而可以将树的形态变为必胜的状态。

我实在是太笨了，以为只有在一条链的情况下才能删，其实只要凑够两个节点就能删，最后没删完就说明先手必胜，否则后手必胜。

CODE：

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int tot=0,h[100005];

int n,x,y,siz[100005],f[100005];

struct Edge{

	int x,next;

}e[200005];

inline void add_edge(int x,int y){

	e[++tot].x=y;

	e[tot].next=h[x],h[x]=tot;

}

bool dfs(int x,int fa){

	siz[x]=1;

	int cnt=0;

	for(int i=h[x];i;i=e[i].next){

		if(e[i].x==fa)continue;

		if(dfs(e[i].x,x))return true;

		if(siz[e[i].x]){

			cnt++,siz[x]=0;

			if(cnt==2)return true;

		}

	}

	return false;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<n;i++){

		scanf("%d%d",&x,&y);

		add_edge(x,y);

		add_edge(y,x);

	}

	printf(dfs(1,0)||siz[1]?"First":"Second");

}

巴特西

[agc014d] Black and White Tree（玄学树D）

Description

Input

Output

题解：

CODE：

最新文章

热门文章