题解：P4096 [HEOI2013] Eden 的博弈树

ljwswr · 2026-07-21 14:37:53 · 题解

本题最大的难度在读题 题目看懂了就不难了。

用 c[u] 表示节点 u 的决策方（0 表示黑方，1 表示白方）。
用 f[u][col] 表示让节点 u 的 col 方（0 表示黑方，1 表示白方）必胜，需要的最小叶子节点数。

对于叶子节点，f[u][0] = 1，f[u][1] = 1。
对于非叶子节点，转移题目里有（c[u] 表示决策方，1 - c[u] 表示非决策方）：

求出 f[u][col] 后，再 DFS 二次，第一次求出最小黑方胜集合的叶子节点，第二次求出最小白方胜集合的叶子节点。
对于每个被遍历到的点（必胜的一方颜色是 col）：

• 如果是叶子节点，直接标记。
• 如果必胜方和决策方相同（col = c[u]），遍历所有 f[v][col] 最小的子节点。
• 如果必胜方和决策方不同（col \ne c[u]），遍历所有子节点。

最后统计所有被黑色和白色同时标记的叶子节点的答案就行了。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f
int n, fa[N], vis[N][2];
int c[N], f[N][2]; //c[u] == 0 黑色
int cnt, xo, mi; //总数、编号异或和、最小编号
vector<int> g[N];

void dfsc(int u) {
    f[u][c[u]] = INF;
    if(!g[u].size()) {
        f[u][0] = 1;
        f[u][1] = 1;
    }
    for(int v : g[u]) {
        c[v] = c[u] ^ 1;
        dfsc(v);
        f[u][c[u]] = min(f[u][c[u]], f[v][c[u]]);
        f[u][1 ^ c[u]] += f[v][1 ^ c[u]];
    }
}

void dfs2(int u, int co) {
    if(!g[u].size()) vis[u][co] = 1;
    for(int v : g[u]) {
        if(c[u] != co) {
            dfs2(v, co);
        } else if(f[v][c[u]] == f[u][c[u]])
            dfs2(v, co);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 2; i <= n; i++) {
        cin >> fa[i];
        g[fa[i]].push_back(i);
    } mi = INF;
    dfsc(1);
    dfs2(1, 0);
    dfs2(1, 1);
    for(int u = 1; u <= n; u++) 
        if(vis[u][0] && vis[u][1]) {
            cnt++;
            xo ^= u;
            mi = min(mi, u);
        } //统计答案
    cout << mi << ' ' << cnt << ' ' << xo;
    return 0;
}