#P17838. 黑白树
黑白树
题目描述
给定一棵以 为根且有 个节点的有根树。
每个结点 均有 表示结点 的颜色为白色或黑色。
Alice 与 Bob 在这棵树上进行游戏。Alice 先手,之后双方轮流操作。
每次操作时,当前玩家必须选择一个黑色节点 ,并依次执行以下操作:
- 将 的颜色修改为白色。
- 从 的子树中除 自身以外的结点组成的集合中,任选一个子集(可以为空集),并改变其中所有结点的颜色(黑变为白,白变为黑)。
若轮到某位玩家操作时不存在黑色节点,则该玩家无法进行操作并输掉游戏。
假设 Alice 和 Bob 均采取最优策略,请判断最终的赢家。
输入格式
第一行一个整数 (),表示测试数据的组数。
对于每组测试数据:
- 第一行一个整数 (保证 ),表示树中的结点数量。
- 第二行 个整数 (),表示结点 的颜色。
- 接下来 行,每行两个整数 和 (),表示结点 与 之间有一条边。
输出格式
对于每组测试数据,输出一行:
- 如果 Alice 存在必胜策略,请输出
- 否则输出
2
3
0 1 1
1 2
1 3
3
1 1 1
1 2
1 3
Bob
Alice
提示
对于第一组测试数据:

无论 Alice 操作结点 还是 ,Bob 都可以操作另一个结点获得胜利。
对于第二组测试数据:

Alice 可以选择对结点 操作,并选择子集 ,直接将所有结点变为白色获得胜利。