Atcoder #017 agc017 D.Game on Tree 树上NIM 博弈

题意：树上NIM的模板题，给出一颗树，现有操作删去端点不为根节点的边，其另一端节点都将被移除，不能取者为败

思路：一看就是个NIM博弈题，只是搬到树上进行，树上DFS进行异或记得#014D题也是博弈...巨水比赛B题没想出来先做了这题:P

/** @Date    : 2017-07-09 21:15:04

  * @FileName: D 树上删边 NIM 博弈.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

vectoredg[N];

int get_sg(int x,int pre)

{

    int ret = 0;

    for(auto i:edg[x])

    {

        if(i!=pre)

            ret^=(1 + get_sg(i, x));

    }

    return ret;

}

int main()

{

 	int n;

    while(~scanf("%d", &n))

    {

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

            edg[i].clear();

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

        {

            int x, y;

            scanf("%d%d",&x, &y);

            edg[x].PB(y);

            edg[y].PB(x);

        }

        if(get_sg(1, -1))

            puts("Alice");

        else

            puts("Bob");

    }

    return 0;

}

巴特西

Atcoder #017 agc017 D.Game on Tree 树上NIM 博弈

最新文章

热门文章