AtCoder Grand Contest 014 D：Black and White Tree

题目传送门：https://agc014.contest.atcoder.jp/tasks/agc014_d

题目翻译

给你一棵树，每次任选一个点染色，先手染白色，后手染黑色。如果最后存在一个白色的点与其相连的点都是白色的，就算先手胜利，否则后手胜利。两人绝顶聪明，\(n\leqslant 10^5\)

题解

假设这颗树存在完美匹配，那么不管先手染哪一个点，后手都能将与其匹配的点染成黑色。也就是说，存在完美匹配的话后手一定胜利。

假设不存在完美匹配，先手每次可以选择一个叶子结点的父亲染色，然后后手肯定只能被迫把叶子结点染成黑色。染完之后这俩点已经没有影响了就可以直接删掉了。因为不存在完美匹配，所以最后肯定会剩下孤立的点，先手把它们任意一个染成白色就赢了。这道题就变成了判断一棵树是否存在完美匹配的题了。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

using namespace std;

const int maxn=1e5+5;

int n,tot;

int now[maxn],pre[maxn<<1],son[maxn<<1];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot,son[tot]=b;

}

int dfs(int fa,int u) {

	int res=0;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa)res+=dfs(u,v);

	if(res>=2)return res;

	else return res^1;

}

int main() {

	n=read();

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

		int a=read(),b=read();

		add(a,b),add(b,a);

	}

	if(dfs(0,1))puts("First");

	else puts("Second");

	return 0;

}

巴特西

AtCoder Grand Contest 014 D：Black and White Tree

题目翻译

题解

最新文章

热门文章