AT_arc162_c [ARC162C] Mex Game on Tree

给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，对于每个 $i\ (2\leq i \leq N)$，顶点 $i$ 的父节点为 $P_i$。 树上的部分顶点上写有 $0$ 到 $N$ 之间的整数。这些信息由数列 $A=(A_1,A_2,\ldots,A_N)$ 给出，若 $A_i\neq -1$，则表示顶点 $i$ 上写有整数 $A_i$；若 $A_i=-1$，则表示顶点 $i$ 上没有写整数。 Alice 和 Bob 进行游戏。Alice 先手，双方轮流操作，直到所有顶点都被写上整数。每次操作可以选择一个尚未写整数的顶点，并在其上写一个 $0$ 到 $N$ 之间的整数。 操作结束后，对于每个顶点 $v$，定义 $f(v)$ 为“在顶点 $v$ 的子树中（包括 $v$ 本身），没有被写下的最小非负整数”。 若存在某个顶点 $v$ 满足 $f(v)=K$，则 Alice 获胜，否则 Bob 获胜。请判断在双方都采取最优策略的情况下，谁会获胜。 有 $T$ 组测试数据，请分别作答。

输入按以下格式从标准输入读入。 > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每组数据格式如下： > $N\ K$ > $P_2\ P_3\ \ldots\ P_N$ > $A_1\ A_2\ \ldots\ A_N$

输出 $T$ 行。对于第 $i$ 组测试数据，若 Alice 获胜则输出 `Alice`，否则输出 `Bob`。

## 限制 - $1\leq T\leq 10^3$ - $2\leq N\leq 10^3$ - $0\leq K\leq N$ - $1\leq P_i < i\ (2\leq i\leq N)$ - $-1\leq A_i\leq N\ (1\leq i\leq N)$ - 所有输入的数均为整数 - 所有测试数据中 $N$ 的总和不超过 $2\times 10^3$ ## 样例解释 1 对于第 $1$ 组测试数据，Alice 可以在顶点 $2$ 上写 $0$，无论 Bob 如何操作，都有 $f(2)=2$，因此 Alice 获胜。对于第 $2$ 组测试数据，Bob 可以通过合理选择写入的整数，使得不存在 $f(v)=4$ 的顶点，因此 Bob 获胜。 由 ChatGPT 4.1 翻译