[ICPC 2021 Jakarta R] White-Black Tree

chen_zhe · 2026-03-04 16:04:28 · 题解

这是官方题解的 AI 中文翻译。

设节点 i 的高度 h_i 为从节点 i 到其某个叶子节点的最长路径上的边数。

此外，设 M_h 为树中高度为 h 的白色节点的数量。当且仅当对于每个可能的 h，M_h 均为偶数时，先手必败。

为什么？观察可知，游戏结束状态（一个必败态）对于每个可能的 h 都有其 M_h 为偶数（确切地说是 0）。如果所有的 M 值都是偶数，那么任何有效的移动都将使至少一个 h 的 M_h 变为奇数。如果存在一个高度 k 使得 M_k 为奇数，那么相应的玩家有一个移动可以使每个可能的 h 的 M_h 变为偶数。具体而言，玩家需要选择一个具有奇数 M_h 的最高白色节点并翻转该节点。然后，玩家需要根据需要翻转其祖先节点，使得剩余的 M_h 变为偶数。

该解法的运行时间为 O(N)。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N;
    scanf("%d", &N);

    vector<vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int P;
        scanf("%d", &P);
        adj[--P].push_back(i);
    }

    vector<int> C(N);
    for (int i = 0; i < N; ++i) scanf("%d", &C[i]);

    vector<int> heights(N);
    for (int u = N - 1; u >= 0; --u) {
        for (int v : adj[u]) {
            heights[u] = max(heights[u], heights[v] + 1);
        }
    }

    vector<int> parities(N);
    for (int u = 0; u < N; ++u) {
        if (C[u]) {
            parities[heights[u]] ^= 1;
        }
    }

    if (any_of(parities.begin(), parities.end(), [](int p) { return p; })) {
        printf("First\n");
    } else {
        printf("Second\n");
    }
}

int main() {
    solve();
    return 0;
}