← 返回题目列表

AtCoder · arc162_c

C. 树上的墨西哥游戏

中文机器翻译题面 查看原题

分数: 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 通过选择正确的整数来写入。