← 返回题目列表

Codeforces · 1404/B

B. 树标签

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

Alice 和 Bob 正在玩一个有趣的树标签游戏。

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

最初,Alice 位于顶点 $$$a$$$,Bob 位于顶点 $$$b$$$。他们轮流行动,爱丽丝率先行动。在一次移动中,Alice 可以跳到距离当前顶点至多 $$$da$$$ 的顶点。在一次移动中,Bob 可以跳到距离当前顶点至多 $$$db$$$ 的顶点。两个顶点之间的距离定义为它们之间唯一简单路径上的边数。特别是,任一玩家都可以在一次移动中停留在同一顶点。请注意,在执行移动时,玩家仅占据其移动的起始和结束顶点,而不是它们之间的顶点。

如果在最多 $$$10^{100}$$$ 移动之后,Alice 和 Bob 占据相同的顶点,则 Alice 被宣布为获胜者。否则,鲍勃获胜。

如果两名玩家都发挥最佳,则确定获胜者。

输入

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

每个测试用例的第一行包含五个整数 $$$n,a,b,da,db$$$ ($$$2\le n\le 10^5$$$, $$$1\le a,b\le n$$$, $$$a\ne b$$$, $$$1\le da,db\le n-1$$$) — 顶点数,Alice 的分别是顶点、鲍勃的顶点、爱丽丝的最大跳跃距离和鲍勃的最大跳跃距离。

以下 $$$n-1$$$ 行描述了树的边缘。这些行的第 $$$i$$$ 包含两个整数 $$$u$$$、$$$v$$$ ($$$1\le u, v\le n, u\ne v$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成树结构。

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

输出

对于每个测试用例,输出一行包含游戏获胜者:“Alice”或“Bob”。

示例

输入 #1

4
4 3 2 1 2
1 2
1 3
1 4
6 6 1 2 5
1 2
6 5
2 3
3 4
4 5
9 3 9 2 5
1 2
1 6
1 9
1 3
9 5
7 9
4 8
4 3
11 8 11 3 3
1 2
11 9
4 9
6 5
2 10
3 2
5 9
8 3
7 4
7 10

输出 #1

Alice
Bob
Alice
Alice

注意

在第一个测试用例中,Alice 可以通过移动到顶点 $$$1$$$ 来获胜。然后,无论鲍勃下一步移动到哪里,爱丽丝都能够在下一步移动到相同的顶点。

在第二个测试用例中,Bob 有以下获胜策略。无论Alice移动到哪里,Bob总是会移动到两个顶点$$$1$$$或$$$6$$$中距离Alice最远的那个。