406594: GYM102452 B Binary Tree

In computer science, a binary tree is a rooted tree in which each node has at most two children. In this problem, let's denote $$$n$$$ as the number of nodes, $$$l$$$ as the number of leaf nodes and $$$h$$$ as the height of the tree (a tree consisting of only a root node has a height of $$$0$$$).

Alice and Bob are playing a game with a binary tree. In this game, Alice and Bob have a binary tree, in which node $$$1$$$ is the root. They take turns to perform operations on the tree, and Alice always takes the first turn. In each operation, the player taking the turn must choose a node $$$p$$$ (any node including the root can be chosen), and remove the subtree rooted at $$$p$$$ from the tree. Obviously, the remaining graph, if not empty, is still a binary tree. Then they continue to play with the resulting tree. To make the game more interesting, there is a restriction on which nodes can be chosen as $$$p$$$: the subtree rooted at $$$p$$$ (the subtree to be removed) must be a perfect full binary tree. Note that a perfect full binary tree is a binary tree in which all interior (non-leaf) nodes have two children and all leaf nodes have the same depth. It can be easily shown that in a perfect full binary tree, the equation $$$l=2^h$$$ holds, so does the equation $$$n=2^{h+1}-1$$$. In particular, a tree consisting of only a root node is also a perfect full binary tree. When a player is unable to perform a legal operation, the game ends and that player loses, which means the other player wins.

Three examples of perfect full binary trees.

Alice and Bob are both very smart and always play optimally. Can you determine who would win the game?

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 5\,000$$$), the number of nodes in the binary tree. The following $$$n - 1$$$ lines each contains two integers $$$x, y$$$ ($$$1 \le x \le n, 1 \le y \le n$$$), which denotes an edge between node $$$x$$$ and $$$y$$$. It is guaranteed that the input graph is a binary tree rooted at node $$$1$$$.

It's guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$50\,000$$$.

For each case, print the string "Alice" in a single line if Alice would win the game, otherwise print the string "Bob".

1
5
1 2
1 3
3 4
3 5

Alice

In the sample case, Alice removes the subtree rooted at node $$$3$$$ in the first turn. Then Bob can only choose $$$p=2$$$, which leaves Alice with only the root node $$$1$$$. Because a tree consisting of only a root node is a perfect full binary tree, Alice can remove the only remaining node and win the game.