← 返回题目列表

AtCoder · ttpc2024_2_n

N. 相邻游戏

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

分数: 100 点

问题陈述

你得到了一棵树 N 顶点。树的顶点已编号 1, 2, \dots, N,以及 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和顶点 v_i.

Alice 和 Bob 玩一个游戏,他们交替用自己的标记标记顶点。最初,没有标记任何顶点。

首先,Alice 选择任意顶点并用她的标记对其进行标记。然后,从鲍勃开始,两名玩家交替执行以下操作。无法采取行动的玩家失败,另一位玩家获胜。

  • 选择一个顶点 v 满足以下条件:
    • 顶点 v 未标记。
    • 存在一个顶点 u 连接到 v 的边使得 u 上标有对手的标记。
  • 标记所选顶点 v 带有自己的标记。

当双方都采取最佳策略以取得胜利时,确定获胜者。

约束

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

输入

输入按以下格式给出:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

输出

如果Alice获胜,输出 Alice。如果 Bob 获胜,则输出 Bob.


示例输入 1

5
1 2
2 3
3 4
2 5

示例输出 1

Alice

例如,考虑以下场景:

  1. Alice 首先标记顶点 1 用她的记号笔。
  2. Bob 标记顶点 2 (顶点 1 被对手标记并连接到顶点 2 的边缘)。
  3. Alice 标记顶点 3 (顶点 2 被对手标记并连接到顶点 3 的边缘)。
  4. Bob 标记顶点 4 (顶点 3 被对手标记并连接到顶点 4 的边缘)。
  5. Alice 标记顶点 5 (顶点 2 被对手标记并连接到顶点 5 的边缘)。
  6. Bob 无法移动。爱丽丝赢了。

在这棵树中,Alice 有获胜策略,所以你应该输出 Alice.


示例输入 2

4
1 2
3 4
3 2

示例输出 2

Bob

示例输入 3

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

示例输出 3

Alice