学步园

第一道删边题，这大概是博弈最后一个没有熟悉的分支了

//HDU-3094.cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <utility>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
//const double pai = acos(-1.0);
const double pai = 3.14159265358979323846;
const int INF = 0x3f3f3f3f;
typedef long long love_live;
int sg[100117];
bool mex[100117];
vector<int> arr[100117]; 

void init(){
    memset(mex, 0, sizeof(mex));
    memset(sg, -1, sizeof(sg));
    return ;
}

int getsg(int x){
    if(sg[x] != -1){
        return sg[x];
    }
    int i, j, k;
    sg[x] = 0;
    mex[x] = 1;
    for(i = 0; i < arr[x].size(); ++i){
        if(mex[arr[x][i]] == 0){
            sg[x] ^= (getsg(arr[x][i]) + 1);
        }
    }
    mex[x] = 0;
    return sg[x];
}

int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
//    freopen("output", "w", stdout);
    freopen("input", "r", stdin);
#endif
    int n, m, i, j, k;
    int t, a, b;
    while(scanf("%d", &t) != EOF){
        while(t--){
            scanf("%d", &n);
            for(i = 0; i <= n; ++i){
                arr[i].clear();
            }
            for(i = 1; i < n; ++i){
                scanf("%d %d", &a, &b);
                arr[a].push_back(b);
                arr[b].push_back(a);
             }
            init();
            if(getsg(1) == 0){
                printf("Bob\n");
            }
            else{
                printf("Alice\n");
            }
        }
    }
return 0;
}