#CF2272F. Tree Reduction Game

Tree Reduction Game

题目描述

Alice 和 Bob 在一棵有 nn 个顶点的树上进行博弈。Alice 先手,随后双方轮流操作。

在任意时刻,树都有一个指定的根。设当前根为 uu。当前玩家必须选择 uu 的一个子节点 vv,并执行以下恰好一种操作:

  1. 将 vv 设为新根。
  2. 删除以 vv 为根的整个子树∗^{\text{∗}}。

此处的父子关系是相对于当前根而言的。

在整个博弈过程中,每个顶点最多成为根一次。

如果某位玩家在其回合没有合法操作,则该玩家失败。

博弈开始前,作为后手的补偿,Bob 可以选择任意顶点作为初始根。

给定这棵树,假设双方都采取最优策略,判定胜者。如果 Bob 能获胜,按升序输出他能选择作为初始根以确保获胜的所有顶点。

∗^{\text{∗}}以顶点 vv 为根的子树,是指所有在到根的简单路径上经过 vv 的顶点构成的集合(包含 vv 自身)。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 nn(2≤n≤5⋅1052 \le n \le 5 \cdot 10^5),表示树的顶点数。

接下来 n−1n-1 行,每行包含两个整数 uu 和 vv(1≤u,v≤n1 \le u,v \le n,u≠vu \ne v),表示顶点 uu 和 vv 之间有一条边。保证给定的图是一棵树。

保证所有测试用例的 nn 之和不超过 5⋅1055 \cdot 10^5。

输出格式

  • 如果 Alice 获胜,输出 Alice。
  • 否则,第一行输出 Bob。第二行输出一个整数 kk,表示 Bob 可选择作为初始根以确保获胜的顶点数。第三行按升序输出 kk 个不同的整数 v1,v2,…,vkv_1,v_2,\ldots,v_k,表示所有这样的顶点。

样例

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 获胜。

在第五个测试用例中,顶点 22、44、66 是 Bob 的必胜选择。以顶点 22 为例说明,另外两种情况对称。

如果 Bob 选择顶点 22 作为初始根,其子节点为 11 和 33。

  • 如果 Alice 将根从 22 换到 11,Bob 可以将根从 11 换到 44(或 66)。
  • 如果 Alice 删除以 11 为根的子树,Bob 删除以 33 为根的子树,使 Alice 没有合法操作。
  • 如果 Alice 将根从 22 换到 33,Bob 删除以 22 为根的子树,同样使 Alice 没有合法操作。
  • 如果 Alice 删除以 33 为根的子树,Bob 删除以 11 为根的子树。

因此,初始根为 22 时 Bob 可强制获胜。由对称性,44 和 66 同理。如果 Bob 选择 11、33、55、77 中的任意一个,Alice 有必胜策略。因此答案为 2,4,62,4,6。