分数: 500 点
问题陈述
你得到了一棵有根的树 N 顶点编号 1 to N。顶点 1 是根,也是顶点的父级 i\ (2\leq i \leq N) is P_i.
有根树的某些顶点具有非负整数 上面写着 0 to 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,爱丽丝获胜。否则,鲍勃获胜。当双方都发挥最佳状态时确定获胜者。
有 T 测试用例。逐一回答。
约束
- 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.
输入
输入由标准输入按以下格式给出:
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-th (1\leq i \leq T) 行应包含 Alice 如果爱丽丝获胜,并且 Bob 如果鲍勃在两名玩家都发挥最佳状态时获胜 i- 第一个测试用例。
示例输入 1
2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1
示例输出 1
Alice Bob
在第一个测试用例中,如果 Alice 写 0 在顶点 2,那么 f(2) = 2 无论 Bob 的操作如何。因此,爱丽丝可以获胜。
在第二个测试用例中,Bob 可以确保不会有顶点 f(v) = 4 通过选择正确的整数来写入。