#CF2272F. Tree Reduction Game
Tree Reduction Game
题目描述
Alice 和 Bob 在一棵有 个顶点的树上进行博弈。Alice 先手,随后双方轮流操作。
在任意时刻,树都有一个指定的根。设当前根为 。当前玩家必须选择 的一个子节点 ,并执行以下恰好一种操作:
- 将 设为新根。
- 删除以 为根的整个子树。
此处的父子关系是相对于当前根而言的。
在整个博弈过程中,每个顶点最多成为根一次。
如果某位玩家在其回合没有合法操作,则该玩家失败。
博弈开始前,作为后手的补偿,Bob 可以选择任意顶点作为初始根。
给定这棵树,假设双方都采取最优策略,判定胜者。如果 Bob 能获胜,按升序输出他能选择作为初始根以确保获胜的所有顶点。
以顶点 为根的子树,是指所有在到根的简单路径上经过 的顶点构成的集合(包含 自身)。
输入格式
每个测试点包含多个测试用例。第一行包含测试用例数 ()。随后是各测试用例的描述。
每个测试用例的第一行包含一个整数 (),表示树的顶点数。
接下来 行,每行包含两个整数 和 (,),表示顶点 和 之间有一条边。保证给定的图是一棵树。
保证所有测试用例的 之和不超过 。
输出格式
- 如果 Alice 获胜,输出
Alice。 - 否则,第一行输出
Bob。第二行输出一个整数 ,表示 Bob 可选择作为初始根以确保获胜的顶点数。第三行按升序输出 个不同的整数 ,表示所有这样的顶点。
样例
6
2
1 2
3
1 2
2 3
5
1 2
1 3
1 4
1 5
5
1 2
2 3
3 4
4 5
7
1 2
2 3
1 4
4 5
1 6
6 7
7
1 2
1 3
2 4
2 5
3 6
3 7
Alice
Bob
1
2
Bob
1
1
Bob
2
2 4
Bob
3
2 4 6
Bob
1
1
说明
在第一个测试用例中,无论 Bob 选择哪个顶点作为初始根,Alice 都能在第一步移除唯一子节点的子树。之后 Bob 没有合法操作,因此 Alice 获胜。
在第五个测试用例中,顶点 、、 是 Bob 的必胜选择。以顶点 为例说明,另外两种情况对称。
如果 Bob 选择顶点 作为初始根,其子节点为 和 。
- 如果 Alice 将根从 换到 ,Bob 可以将根从 换到 (或 )。
- 如果 Alice 删除以 为根的子树,Bob 删除以 为根的子树,使 Alice 没有合法操作。
- 如果 Alice 将根从 换到 ,Bob 删除以 为根的子树,同样使 Alice 没有合法操作。
- 如果 Alice 删除以 为根的子树,Bob 删除以 为根的子树。
因此,初始根为 时 Bob 可强制获胜。由对称性, 和 同理。如果 Bob 选择 、、、 中的任意一个,Alice 有必胜策略。因此答案为 。