33OJ
登录 注册

#P17838. 黑白树

    ID: 20514 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>博弈论上海O2优化2026高校校赛

黑白树

题目描述

给定一棵以 11 为根且有 nn 个节点的有根树。

每个结点 uu 均有 colu∈{0,1}col_u \in \{0,1\} 表示结点 uu 的颜色为白色或黑色。

Alice 与 Bob 在这棵树上进行游戏。Alice 先手,之后双方轮流操作。

每次操作时,当前玩家必须选择一个黑色节点 uu,并依次执行以下操作:

  1. 将 uu 的颜色修改为白色。
  2. 从 uu 的子树中除 uu 自身以外的结点组成的集合中,任选一个子集(可以为空集),并改变其中所有结点的颜色(黑变为白,白变为黑)。

若轮到某位玩家操作时不存在黑色节点,则该玩家无法进行操作并输掉游戏。

假设 Alice 和 Bob 均采取最优策略,请判断最终的赢家。

输入格式

第一行一个整数 TT(1≤T≤2×1051 \leq T \leq 2 \times 10^5),表示测试数据的组数。

对于每组测试数据:

  • 第一行一个整数 nn(保证 1≤∑n≤2×1051 \leq \sum n \leq 2 \times 10^5),表示树中的结点数量。
  • 第二行 nn 个整数 colicol_i(coli∈{0,1}col_i \in \{0,1\}),表示结点 ii 的颜色。
  • 接下来 n−1n-1 行,每行两个整数 uu 和 vv(1≤u,v≤n1 \le u,v \le n),表示结点 uu 与 vv 之间有一条边。

输出格式

对于每组测试数据,输出一行:

  • 如果 Alice 存在必胜策略,请输出 Alice\texttt{Alice}
  • 否则输出 Bob\texttt{Bob}
2
3
0 1 1
1 2
1 3
3
1 1 1
1 2
1 3
Bob
Alice

提示

对于第一组测试数据:

无论 Alice 操作结点 22 还是 33,Bob 都可以操作另一个结点获得胜利。

对于第二组测试数据:

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