← 返回题目列表

AtCoder · pakencamp_2025_day3_p

P. 简单的树绘画游戏

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

配点 : 100 点

致环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了


問題文

在顶部 编号为 1 减去 N 它是一个具有 N 给出一棵顶点树。i 第一条边是顶点 u_i 和边 v_i 是平局。爱丽丝和鲍勃在这棵树上玩游戏。 起初,爱丽丝处于顶部。 a ,Bob 是顶点 我在 b 。顶点 a 为红色且顶点 b 为蓝色,其他顶点未着色。

Alice 主导,Alice 和 Bob 轮流执行以下操作。这个操作需要每个玩家 重复直到每 10^{100} 次。

  • 与当前所在顶点相邻的顶点 1 选择一个并移动到该顶点。然后,如果您是 Alice,则将移动的顶点的颜色重新绘制为红色;如果您是 Bob,则将其绘制为蓝色(如果已经着色,则覆盖)。

当所有操作完成后,如果画成蓝色的顶点数大于画成红色的顶点数,则Bob获胜;否则(涂成红色的顶点数大于或等于涂成蓝色的顶点数),Alice 获胜。

当双方都为自己的胜利采取最佳行动时确定谁获胜。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le a, b \le N
  • a \neq b
  • 1 \le u_i, v_i \le N
  • 给定的图是一棵树。
  • 所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。

N a b
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

如果Alice有获胜方法 Alice ,如果鲍勃有获胜方法 Bob 。


入力例 1

5 1 5
4 3
4 5
3 2
2 1

出力例 1

Bob

入力例 2

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

出力例 2

Bob