Problem Statement

There is a tree with N vertices numbered 1,2,…,N. The edges of the tree are denoted by (xi,yi).

On this tree, Alice and Bob play a game against each other. Starting from Alice, they alternately perform the following operation:

• Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex 1.

A player loses the game when he/she is unable to perform the operation. Determine the winner of the game assuming that both players play optimally.

Constraints

• 2≤N≤100000
• 1≤xi,yi≤N
• The given graph is a tree.

Sample Input 1

5

1 2

2 3

2 4

4 5

Sample Output 1

Alice

If Alice first removes the edge connecting Vertices 1 and 2, the tree becomes a single vertex tree containing only Vertex 1. Since there is no edge anymore, Bob cannot perform the operation and Alice wins.

Sample Input 2

5

1 2

2 3

1 4

4 5

Sample Output 2

Bob

Sample Input 3

6

1 2

2 4

5 1

6 3

3 2

Sample Output 3

Alice

Sample Input 4

7

1 2

3 7

4 6

2 3

2 4

1 5

Sample Output 4

Bob

在树上的博弈，从0，1开始看看这棵树的异或和

#include <bits/stdc++.h>

using namespace std;

const int N=;

vector<int>vec[N];

int dfs(int u,int fa) {

    int re=;

    for(int i=; i<vec[u].size(); i++) {

        if(vec[u][i]!=fa) {

            re^=+dfs(vec[u][i],u);

        }

    }

    return re;

}

int main() {

        int n;

        scanf("%d",&n);

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

            int a,b;

            scanf("%d%d",&a,&b);

            vec[a].push_back(b);

            vec[b].push_back(a);

        }

    printf(dfs(,)?"Alice\n":"Bob\n");

    return ;

}