← 返回题目列表

Codeforces · 2013/F2

F2. 树上的游戏(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,不保证 $$$u = v$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Alice 和 Bob 正在树上玩一个有趣的游戏。该游戏在具有 $$$n$$$ 个顶点的树上进行,编号从 $$$1$$$ 到 $$$n$$$。回想一下,具有 $$$n$$$ 顶点的树是具有 $$$n - 1$$$ 边的无向连通图。

Alice 和 Bob 轮流,Alice 先走。每个玩家都从某个顶点开始。

在他们的回合中,玩家必须从当前顶点移动到尚未被任何人访问过的相邻顶点。第一个无法采取行动的玩家失败。

给定两个顶点 $$$u$$$ 和 $$$v$$$。将顶点 $$$u$$$ 到 $$$v$$$ 的简单路径表示为数组 $$$p_1, p_2, p_3, \ldots, p_m$$$,其中 $$$p_1 = u$$$, $$$p_m = v$$$,并且对于所有 $$$i$$$,$$$p_i$$$ 和 $$$p_{i + 1}$$$ 之间有一条边($$$1 \le i < m$$$)。

对于每个 $$$j$$$(其中 $$$1 \le j \le m$$$),如果 Alice 从顶点 $$$1$$$ 开始,Bob 从顶点 $$$p_j$$$ 开始,则需要确定游戏的获胜者。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$),表示顶点 $$$a$$$ 和 $$$b$$$ 之间的无向边。保证这些边形成一棵树。

每个测试用例的最后一行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$2 \le u, v \le n$$$)。

保证从$$$u$$$到$$$v$$$的路径不经过顶点$$$1$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$m$$$ 行。

在第 $$$i$$$ 行中,如果 Alice 从顶点 $$$1$$$ 开始并且 Bob 从顶点 $$$p_i$$$ 开始,则打印游戏的获胜者。如果 Alice 获胜,则打印“Alice”(不带引号),否则打印“Bob”(不带引号)。

示例

输入 #1

3
3
1 2
2 3
2 3
6
1 2
1 3
2 4
2 5
1 6
4 5
4
1 2
1 3
2 4
2 4

输出 #1

Bob
Alice
Alice
Bob
Alice
Bob
Alice

注意

第一个示例中的树。

在第一个测试用例中,路径将为 ($$$2,3$$$)。如果鲍勃从顶点 $$$2$$$ 开始,爱丽丝将无法在第一回合移动到任何地方,并且会失败。

但是,如果 Bob 从顶点 $$$3$$$ 开始,Alice 将移动到顶点 $$$2$$$,而 Bob 将没有剩余的顶点可供访问,并且会失败。