自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:14:29，当前版本为作者最后更新于2019-12-13 18:58:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\ \ \ \ \ \ \$原题解blog

---

$\ \ \ \ \ \ \$题意转化：有一棵以 1 为根的树，每个节点的初始颜色为白色。Alice 先让任意一个节点放上标记变黑作为一次操作。然后 Bob 开始，轮流移动这个标记到当前所在节点的任意一个白色的祖先或者后代节点，并且把它这个节点染成黑色。谁不能移动谁就输了。

$\ \ \ \ \ \ \$考虑这个树上博弈问题。首先引进树的最大匹配。不会的同学，可以自查博客。

$\ \ \ \ \ \ \$首先假设我们只能够走到相邻的节点，我们发现我们只需要判断这棵树是否满足，它的最大匹配是一个完美匹配。如果是的话，后手必胜，否则先手一定能够避免，于是先手必胜。

$\ \ \ \ \ \ \$回到问题，我们不只是走到相邻的节点。但是思路相同，这个问题我们用树形 dp 求解。

$\ \ \ \ \ \ \$定义 $dp_i$ 为节点 $i$ 以及该节点对应子树未匹配节点的最小数量，$cnt=\sum_{\texttt{以i为根节点的后代j}} dp_j$

$$\begin{cases} dp_i = cnt - 1 (cnt > 0), \\ dp_i = 1 (cnt = 0). \\ \end{cases}$$

$\ \ \ \ \ \ \$如果 $dp_1=0$ ，则说明先手必胜。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
vector<int> G[100005];
int dp[100005],n;
bool vis[100005];
void dfs(int now,int pre)
{
	bool flag=false;
	for(unsigned int i=0;i<G[now].size();++i)
	{
		if(G[now][i]==pre)	continue;
		dfs(G[now][i],now);
		flag|=vis[G[now][i]];
		dp[now]+=max(dp[G[now][i]],vis[G[now][i]]?1:0);
	}
	if(!flag || dp[now]>0)	vis[now]=true;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(dp,-1,sizeof dp);
	dfs(1,0);
	puts(dp[1]?"Alice":"Bob");
	return 0;
}