hdu3094 A tree game----树的删边游戏

A tree game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 314 Accepted Submission(s): 146

Problem Description
Alice and Bob want to play an interesting game on a tree.
Given is a tree on N vertices, The vertices are numbered from 1 to N. vertex 1 represents the root. There are N-1 edges. Players alternate in making moves, Alice moves first. A move consists of two steps. In the first step the player selects an edge and removes it from the tree. In the second step he/she removes all the edges that are no longer connected to the root. The player who has no edge to remove loses.
You may assume that both Alice and Bob play optimally.

Input
The first line of the input file contains an integer T (T<=100) specifying the number of test cases.
Each test case begins with a line containing an integer N (1<=N<=10^5), the number of vertices,The following N-1 lines each contain two integers I , J, which means I is connected with J. You can assume that there are no loops in the tree.

Output
For each case, output a single line containing the name of the player who will win the game.

Sample Input
3
3
1 2
2 3

3
1 2
1 3

10
6 2
4 3
8 4
9 5
8 6
2 7
5 8
1 9
6 10

Sample Output
Alice
Bob
Alice

Source
2009 Multi-University Training Contest 18 - Host by ECNU

Recommend
lcy

题意：每次选择一条边删去，并把不和根连的边移去。
据说是贾志豪神牛的论文。
结论：叶子节点的sg值为0，中间节点的SG值为它的所有子节点的SG值加1 后的异或和。
[cpp]
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<memory.h>
#include<vector>
using namespace std;
vector<int>v[100005];
int dfs(int x,int pre)
{
    int ans=0;
    for(int i=0;i<v[x].size();i++)
    {
        //printf("%d %d %d \n",x,i,v[x][i]);
        if(v[x][i]!=pre)
        {
            ans^=(1+dfs(v[x][i],x));
        }
    }
    return ans;
}
int main()
{
    int t,a,b,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        v[i].clear();
        n--;
        while(n--)
        {
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        //printf("%d\n",v[1][2]);
        if(dfs(1,-1)) puts("Alice");
        else puts("Bob");
    }
}

补充：软件开发 , C++ ,