AGC014 D Black and White Tree（博弈论）

题目大意：

给出一个n个结点的树，A可以把树上的结点涂成白色，B可以把树上的结点涂成黑色，A和B交题涂色，全部涂完以后，B进行这样的操作

把树上所有与黑色结点相邻的点全部涂成白色

如果这样树上还有白色，那么A赢，否则B赢

(n <= 10^5)

题解：

我是这么考虑的，A需要一直保持主动才有机会赢

保持主动的意思就是说，A如果把一个点涂成白色，那么B必须把其附近的一个点涂成黑色，否则B就会输

如何保持主动呢？其实很简单，首先把树变成以1为根节点的树

然后如果A把叶子结点的父结点涂成白色，那么B一定要把叶节点涂成黑色。

同时可以证明这样做一定会更优，因为白色结点在黑色结点的上方。

所以A保持主动总是更优的。

如何判断输赢呢？

一个简单的条件是如果一个结点涂成白色以后，它有2个叶子结点，那么就是A赢

因为B无法同时涂2个叶子结点

根据这个，就有这样的做法

就是先把所有叶子结点的父结点都涂成白色，然后这个过程中如果有一个结点被涂了两遍，那么就是A赢

如果没有，就把这些染色的结点都删去，这样又会多很多叶子结点，继续向上这么做即可

注意对根节点的处理（或许不处理也可以通过）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 100;
queue<int> Q;
vector<int> G[maxn];
int f[maxn], col[maxn], in[maxn];
void dfs(int x, int fa){
    f[x] = fa;
    for(auto to : G[x]){
        if(to == fa) continue;
        dfs(to, x);
    }
}
int n, x, y;
int main()
{
    cin>>n;
    for(int i = 0; i < n-1; i++){
        cin>>x>>y;
        in[x]++; in[y]++;
        G[x].pb(y); G[y].pb(x);
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        if(in[i] == 1) Q.push(i);
    }
    int label = 0;
    f[1] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        if(col[x]) continue;
        if(col[f[x]]) label = 1;
        else{
            col[f[x]] = 1;
            in[f[f[x]]]--;
            if(in[f[f[x]]] == 0) label = 1;
            if(in[f[f[x]]] == 1 && f[f[x]] != 1) Q.push(f[f[x]]);
        }
    }
    cout<<(label ? "First" : "Second")<<endl;
    return 0;
}