发现如果子树内如果存在 \(k\) 则 \(mex\) 的值必定不为 \(k\)，所以 Bob 的策略即为在空位填上 \(k\)。
Alice 的决策便可以知道是在 Bob 出手前就要让这个子树满足条件，不让 Bob 破坏这个子树，考虑需满足哪些条件：
- 至多 \(1\) 个空位，否则 Bob 可以把 \(k\) 填在子树中。
- 子树内本身没有颜色为 \(k\) 的点。
- 空位填上合适的颜色能使 \(0\sim k - 1\) 的颜色都在子树内出现。
这些条件暴力统计即可。
若满足条件，则 Alice 胜，否则 Bob 胜。
时间复杂度 \(O(n(n + k))\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: C - Mex Game on Tree
// Contest: AtCoder - AtCoder Regular Contest 162
// URL: https://atcoder.jp/contests/arc162/tasks/arc162_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
basic_string<int> G[N];
int col[N];
int mex[N];
int main() {
function<void ()> solve = []() -> void {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 2; i <= n; i++) {
int f;
scanf("%d", &f);
G[f] += i;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &col[i]);
}
int Yes = 0;
function<int (int)> dfsmex = [&dfsmex, &k](int u) -> int {
int tot = (col[u] == -1);
if ((~ col[u]) && col[u] <= k) {
mex[col[u]] = 1;
}
for (int v : G[u]) {
tot += dfsmex(v);
}
return tot;
};
function<void (int)> dfs = [&dfs, &dfsmex, &Yes, &k](int u) -> void {
for (int v : G[u]) {
dfs(v);
}
for (int i = 0; i <= k; i++) {
mex[i] = 0;
}
int tot = dfsmex(u);
int cnt = 0;
for (int i = 0; i < k; i++) {
cnt += (mex[i] == 0);
}
if (((tot == 1 && cnt <= 1) || (tot == 0 && cnt == 0)) && (! mex[k])) {
Yes = 1;
}
return ;
};
dfs(1);
printf("%s\n", Yes ? "Alice" : "Bob");
return ;
};
int _;
scanf("%d", &_);
for (; _; _--) {
solve();
}
return 0;
}