P5801 [SEERC 2019] Game on a Tree

Alice and Bob play a game on a tree. At the beginning, all nodes on the tree are white. Alice moves first. She may choose any node and place a token on it, and that node becomes black. After that, the players take turns. In each turn, the current player may move the token from its current node to a white ancestor of that node or to a white child of that node, and the node moved to becomes black. The player who cannot make a move loses. In a rooted tree, an *ancestor* of a node $v$ is any node on the path from the root to node $v$. In a rooted tree, a *child* of a node $v$ is a node $w$ such that $v$ is on the path from the root to $w$ and $v$ is the parent of $w$. The root of the tree is node $1$.

The first line contains an integer $n \ (1 \leq n \leq 100 \ 000)$, the number of nodes in the tree. Each of the next $n-1$ lines contains two integers $u$ and $v \ (1 \leq u, v \leq n)$, denoting an edge $(u, v)$ of the tree. The testdata guarantees that these edges form a tree.

Output one line. If Alice wins the game, output `Alice`; otherwise, output `Bob`.

In the first sample, the tree is a chain of $4$ nodes, so Bob can always move the token to the last remaining white node. In the second sample, Alice’s best strategy is to place the token on node $3$ first, and then node $3$ becomes black. Bob can only move the token to node $1$. Alice can choose node $4, 5, 6$ or $7$ to move to. Bob can then only choose node $2$. After Alice chooses any white child of node $2$, Bob will have no move. Translated by ChatGPT 5