[ARC162] C - Mex Game on Tree
[Q] https://atcoder.jp/contests/arc162/tasks/arc162_c
考察
・BobはKの値を書くのが強い。
AliceがK=2を作りたい場合、部分木は{0, 1}で構成されている必要がある。
Bobが妨害してK=2を置いて{0, 1, 2}としてしまえば、必ずKは3以上にできるので、部分木を殺せる。
・Aliceが勝つには？
こんな部分木が存在すれば勝てそう。
ex, K=2のとき
1. 部分木が{0, 1}で構成されていて、-1がない場合はすでに確定。
2. 部分木が{0}で構成されていて、-1が1個ある場合。-1を1にしてしまえば確定。
3. 部分木が{1}で構成されていて、-1が1個ある場合。-1を0にしてしまえば確定。
・Aliceが満たせないような部分木は？
1. 部分木に{2}が含まれている。
2. -1が2個以上ある場合。後追いで{2}を書かれてしまう。
1つでも勝てる部分木を探せばいい。
また、Nの総数がたったの2000しかない。
難しいことは考えずに、すべての頂点から見た部分木を全部シミュレートすることが可能。
・実装重くなりそうだけど頑張る。
実装
int main() {
ll T;
cin >> T;
rep(_t, T) {
ll N, K;
cin >> N >> K;
vector<ll> G[N]; // 根から葉
vector<ll> R[N]; // 葉から根
vector<set<ll>> S(N); // 部分木に含まれている要素を除いた集合
set<ll> _s;
rep(i, N + 3) _s.emplace(i);
rep(i, N) S[i] = _s;
for (ll i = 1; i < N; ++i) {
ll p;
cin >> p;
--p;
G[p].emplace_back(i); // 根から葉
R[i].emplace_back(p); // 葉から根
}
vector<ll> A(N);
vector<ll> F(N, 0); // -1の数
for (auto &a : A) cin >> a;
// 毎回根まで戻って、各頂点の部分木の値をメモしていく
auto back_root = [&](ll s) {
ll a = A[s];
while (1) {
if (a == -1)
++F[s];
else {
S[s].erase(a);
}
if (s == 0) return;
s = R[s][0];
}
};
std::function<void(ll)> dfs = [&](ll v) {
back_root(v);
for (auto w : G[v]) {
dfs(w);
}
};
dfs(0);
bool is_bob = true;
rep(i, N) {
if (*S[i].begin() == K && F[i] <= 1) { // 部分木の最小値がKで、-1が1個以下なら確定
is_bob = false;
break;
}
{
auto it = S[i].begin();
++it;
if (*it == K && F[i] == 1) { // -1が1つで、1つ補完してKになる場合確定。
is_bob = false;
break;
}
}
}
if (is_bob) {
cout << "Bob" << endl;
} else {
cout << "Alice" << endl;
}
}
}