P17838 黑白树
题目描述
给定一棵以 $1$ 为根且有 $n$ 个节点的有根树。
每个结点 $u$ 均有 $col_u \in \{0,1\}$ 表示结点 $u$ 的颜色为白色或黑色。
Alice 与 Bob 在这棵树上进行游戏。Alice 先手，之后双方轮流操作。
每次操作时，当前玩家必须选择一个黑色节点 $u$，并依次执行以下操作：
1. 将 $u$ 的颜色修改为白色。
2. 从 $u$ 的子树中除 $u$ 自身以外的结点组成的集合中，任选一个子集（可以为空集），并改变其中所有结点的颜色（黑变为白，白变为黑）。
若轮到某位玩家操作时不存在黑色节点，则该玩家无法进行操作并输掉游戏。
假设 Alice 和 Bob 均采取最优策略，请判断最终的赢家。
输入格式
第一行一个整数 $T$（$1 \leq T \leq 2 \times 10^5$），表示测试数据的组数。
对于每组测试数据：
- 第一行一个整数 $n$（保证 $1 \leq \sum n \leq 2 \times 10^5$），表示树中的结点数量。
- 第二行 $n$ 个整数 $col_i$（$col_i \in \{0,1\}$），表示结点 $i$ 的颜色。
- 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \le u,v \le n$），表示结点 $u$ 与 $v$ 之间有一条边。
输出格式
对于每组测试数据，输出一行：
- 如果 Alice 存在必胜策略，请输出 $\texttt{Alice}$
- 否则输出 $\texttt{Bob}$
说明/提示
对于第一组测试数据：
无论 Alice 操作结点 $2$ 还是 $3$，Bob 都可以操作另一个结点获得胜利。
对于第二组测试数据：
Alice 可以选择对结点 $1$ 操作，并选择子集 $\{2,3\}$，直接将所有结点变为白色获得胜利。