原文链接https://www.cnblogs.com/zhouzhendong/p/AGC017D.html

题目传送门 - AGC017D

题意

　　给定一棵 n 个节点的以节点 1 为根的树。

　　两个人在博弈，每次可以删除任意一个子树，不能删掉整个树。最终不能操作的人输。

　　问先手是否必胜。

　　$n\leq 10^5$

题解

　　考虑处理出每一个节点的 SG 值。

　　对于节点 x ，显然他的所有子树都是独立的，我们只需要求出所有子树的 SG 值然后异或起来就好了。

　　假设 y 为 x 的一个儿子，则节点 y 对于 x 的贡献是什么呢？

　　显然不是 SG[y] ，因为 x 到 y 还有一条边。在 y 子树中操作的任何时候都可以直接删除这条边到达状态 0 ，相当于 y 子树的所有状态都连了一条到 0 的边。

　　所以 SG'[y] = SG[y] + 1 。

　　所以 SG[x] 就是所有的 SG'[y] 的异或值（其中 y 为 x 的儿子）。

代码

#include <bits/stdc++.h>

#define y1 __zzd001

using namespace std;

typedef long long LL;

LL read(){

	LL x=0;

	char ch=getchar();

	while (!isdigit(ch))

		ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return x;

}

const int N=100005;

int n,sg[N];

vector <int> e[N];

void solve(int x,int pre){

	sg[x]=0;

	for (auto y : e[x])

		if (y!=pre){

			solve(y,x);

			sg[x]^=sg[y]+1;

		}

}

int main(){

	n=read();

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

		int x=read(),y=read();

		e[x].push_back(y);

		e[y].push_back(x);

	}

	solve(1,0);

	puts(sg[1]?"Alice":"Bob");

	return 0;

}

巴特西

AtCoder Grand Contest 017D (AGC017D) Game on Tree 博弈

题目传送门 - AGC017D

题意

题解

代码

最新文章

热门文章