【AtCoder2376】Black and White Tree（博弈）

题意

A和B轮流给树上的结点染色，A每次选择没染过的点染成白色，B每次选择没染过的点染成黑色，最后若所有白色都与黑色相邻，则B胜，否则A胜。双方以最优策略，求A胜还是B胜。

题解

A首先选择叶子结点的父亲u，则B只能选择叶子结点（否则叶子节点染白后，永远不可能与黑色相邻），所以，如果存在u有两个以上叶子结点，则A胜；
然后删去u，则u的父亲v，如果v没有了子节点，v就成为新的叶子结点，A可继续先前的操作，B永远处于被动当中。
当遇到一下两种情况时，A必胜

• 当前结点u含有两个或以上叶子结点
• 若u为根，且u的所有子节点都被染为白色（这时把自己染为白色即可）

dfs处理一边即可。

代码

#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int MAXN=100005; int N; vector<int> adj[MAXN]; int col[MAXN]; bool dfs(int u,int f) {
      if(adj[u].size()==1U) {
      col[u]=0;//标记为叶子结点 return false; } int cnt[2]={
     0}; for(int i=0;i<(int)adj[u].size();i++) {
      int v=adj[u][i]; if(v==f) continue; if(dfs(v,u)) return true; cnt[col[v]]++; } if(cnt[0]>=2) return true;//叶子结点大于等于2 if(f==0&&(int)adj[u].size()==cnt[1]) return true;//当前u为根，u的所有子节点均为白色 if(cnt[0]) col[u]=1;//如果有叶子结点，这个点染白 else col[u]=0;//这个点的子节点全部被染白（被删去），当前u变为叶子结点 return false; } int main() {
      scanf("%d",&N); for(int i=1;i<N;i++) {
      int u,v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } if(N==2) puts("Second"); else {
      bool ans; for(int i=1;i<=N;i++) if(adj[i].size()>1U) {
      ans=dfs(i,0); break; } puts(ans?"First":"Second"); } return 0; }