题解 P5801 【[SEERC2019]Game on a Tree】
FjswYuzu
·
·
题解
---
$\ \ \ \ \ \ \ $题意转化：有一棵以 1 为根的树，每个节点的初始颜色为白色。Alice 先让任意一个节点放上标记变黑作为一次操作。然后 Bob 开始，轮流移动这个标记到当前所在节点的任意一个白色的祖先或者后代节点，并且把它这个节点染成黑色。谁不能移动谁就输了。
$\ \ \ \ \ \ \ $考虑这个树上博弈问题。首先引进树的最大匹配。不会的同学，可以自查博客。
$\ \ \ \ \ \ \ $首先假设我们只能够走到相邻的节点，我们发现我们只需要判断这棵树是否满足，它的最大匹配是一个完美匹配。如果是的话，后手必胜，否则先手一定能够避免，于是先手必胜。
$\ \ \ \ \ \ \ $回到问题，我们不只是走到相邻的节点。但是思路相同，这个问题我们用树形 dp 求解。
$\ \ \ \ \ \ \ $定义 $dp_i$ 为节点 $i$ 以及该节点对应子树未匹配节点的最小数量，$cnt=\sum_{\texttt{以i为根节点的后代j}} dp_j
dp_i = cnt - 1 (cnt > 0), \\ dp_i = 1 (cnt = 0). \\
\end{cases}
```cpp
#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;
}
```