AT_arc162_c.[ARC162C] Mex Game on Tree

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一棵有 $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

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

限制

对于第 $1$ 组测试数据，Alice 可以在顶点 $2$ 上写 $0$ ，无论 Bob 如何操作，都有 $f(2)=2$ ，因此 Alice 获胜。对于第 $2$ 组测试数据，Bob 可以通过合理选择写入的整数，使得不存在 $f(v)=4$ 的顶点，因此 Bob 获胜。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?