Atcoder D - Black and White Tree（树dp+博弈）

题目链接：http://agc014.contest.atcoder.jp/tasks/agc014_d

题意：有一棵树先手涂白色，后手涂黑色，直到不能再涂为止。涂完后再把所有黑色直接相邻的白色都变成黑色。

如果最后还有白色那么是先手赢，否则是后手赢。

题解：先不管这是一棵树直接放在一条直线上考虑，显然奇数个点是先手赢，偶数个点是后手赢。因为，想要有

白色一定要白色多涂一次才行，这是最起码的。

然后再放到树上考虑。以一个点为根节点，如果子节点的个数为奇数的子树超过两条那么肯定是先手赢，因为算

上根节点至少有一个是奇数点有一个偶数点，偶数点会全都变成黑色但是奇数点肯定有白色留下。

最后看一下代码好好理解一下。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

using namespace std;

const int M = 1e5 + 10;

vector<int> vc[M];

int dfs(int pos , int pre) {

    int len = vc[pos].size();

    int res = 0;

    for(int i = 0 ; i < len ; i++) {

        int v = vc[pos][i];

        if(v != pre) {

            res += dfs(v , pos);

        }

    }

    if(res >= 2) {

        printf("First\n");

        exit(0);

    }

    else if(res == 0) return 1;

    else return 0;

}

int main() {

    int n , u , v;

    scanf("%d" , &n);

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

        scanf("%d%d" , &u , &v);

        vc[u].push_back(v);

        vc[v].push_back(u);

    }

    int ans = dfs(1 , -1);

    if(ans) {

        printf("First\n");

    }

    else {

        printf("Second\n");

    }

    return 0;

}

巴特西

Atcoder D - Black and White Tree（树dp+博弈）

最新文章

热门文章