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

LINK

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

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

/** @Date    : 2017-07-09 21:15:04
  * @FileName: D 树上删边 NIM 博弈.cpp
  * @Platform: Windows
  * @Author  : Lweleth ([e-mail])
  * @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;
}