Game on Tree

D - Game on Tree

Time limit : 2sec / Memory limit : 256MB

Score : 1100 points

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.

Input

Input is given from Standard Input in the following format:

N
x1 y1
x2 y2
:
xN−1 yN−1

Output

Print Alice if Alice wins; print Bob if Bob wins.

Sample Input 1

Copy

Sample Output 1

Copy

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

Copy

Sample Output 2

Copy

Bob

Sample Input 3

Copy

Sample Output 3

Copy

Alice

Sample Input 4

Copy

Sample Output 4

Copy

Bob

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

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>vec[N];
int dfs(int u,int fa) {
    int re=0;
    for(int i=0; i<vec[u].size(); i++) {
        if(vec[u][i]!=fa) {
            re^=1+dfs(vec[u][i],u);
        }
    }
    return re;
}
int main() {
        int n;
        scanf("%d",&n);
        for(int i=1; i<n; i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
    printf(dfs(1,0)?"Alice
":"Bob
");
    return 0;
}