CF1404B Tree Tag

Alice 和 Bob 正在玩一个有趣的“树上捉迷藏”游戏。 游戏在一棵有 $n$ 个顶点的树上进行，顶点编号从 $1$ 到 $n$。回忆一下，一棵 $n$ 个顶点的树是一个无向、连通且有 $n-1$ 条边的图。 最开始，Alice 位于顶点 $a$，Bob 位于顶点 $b$。他们轮流行动，Alice 先手。在每一次行动中，Alice 可以跳到距离当前位置不超过 $da$ 的任意顶点。同理，Bob 在每次行动中可以跳到距离当前位置不超过 $db$ 的任意顶点。两个顶点之间的距离定义为它们之间唯一简单路径上的边数。特别地，任一玩家在行动时可以选择留在原地。注意，玩家在移动时只会占据起点和终点，不会经过中间的顶点。 如果在不超过 $10^{100}$ 步内，Alice 和 Bob 占据了同一个顶点，则 Alice 获胜。否则，Bob 获胜。 请判断在双方都采取最优策略的情况下，谁会获胜。

每组测试数据包含多个测试用例。第一行包含测试用例数 $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 的起始顶点、Bob 的起始顶点、Alice 的最大跳跃距离和 Bob 的最大跳跃距离。 接下来的 $n-1$ 行，每行包含两个整数 $u, v$（$1 \le u, v \le n, u \ne v$），表示顶点 $u$ 和顶点 $v$ 之间有一条边。保证这些边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行，内容为游戏的获胜者："Alice" 或 "Bob"。

在第一个测试用例中，Alice 可以移动到顶点 $1$。无论 Bob 下一步移动到哪里，Alice 都能在下一步移动到同一个顶点，从而获胜。  在第二个测试用例中，Bob 有如下的制胜策略：无论 Alice 移动到哪里，Bob 总是移动到顶点 $1$ 或 $6$ 中距离 Alice 最远的那个。  由 ChatGPT 4.1 翻译