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

· · 题解

原题链接

题意

有一棵 n 个节点的树，1 号是根。根是黑方决策点，每个节点的决策方与该节点的父亲决策方相反。每个叶子可以自由设为黑胜或白胜。

非叶子节点胜利规则：

定义“最小黑方胜集合”：选一些叶子设为黑胜，能让根变成黑胜，且选的叶子数量最少的叶子的集合。“最小白方胜集合”同理。

关键叶节点即为既属于某个最小黑方胜集合，又属于某个最小白方胜集合的叶子节点、

现在需要求出编号最小的关键叶节点、关键叶节点数量、关键叶节点的编号异或和。

思路

设 f_{u, c} 表示让子树 u 最终为颜色 c（0 黑 1 白，其实 0 白 1 黑也可以，代码本身没有区别，只有理解的区别）胜所需的最少叶子数。叶子本身代价为 1。

非叶子节点按决策方与目标是否相同分两种情况转移：

两次 dfs 分别求出 c = 0 和 c = 1 时的最小代价 f_{1, c} 及各子树代价。

那么我们就可以回溯找出可能属于最小集合的叶子节点了。从根出发 dfs，若当前节点 f_{u, c} = \infty 则不可达，直接返回。对于 col_u = c 的节点，所有 f_{v, c} = f_{u, c} 的儿子都可能被选中，递归进入；对于 col_u \ne c 的节点，所有 f_{v, c} \ne \infty 的儿子都必须被选中，递归进入。叶子直接标记。

用两个数组 vis_0 和 vis_1 分别记录 c = 0 和 c = 1 时被标记的叶子。最后两个 vis 都标记了的即为关键叶节点。统计个数、最小编号和异或和即可。

时空复杂度

时间复杂度：O(n)。

空间复杂度：O(n)。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 5;
const int INF = 1e9;

int n, f[N][2], col[N], vis[2][N], ans, cnt;
vector<int> g[N];

void dfs(int u, int c) {
  bool flag = 0;
  for (int v : g[u]) {
    col[v] = col[u] ^ 1;
    dfs(v, c);
    if (col[u] == c) {
      f[u][c] = min(f[u][c], f[v][c]);
    } else if (f[v][c] == INF) {
      f[u][c] = INF;
      flag = 1;                                // col[u] != c 且有儿子节点不可达，则该节点也不可达（无解）
    } else if (!flag) {                        // 必须有解才可以累加该节点的答案
      f[u][c] = f[u][c] == INF ? 0 : f[u][c];
      f[u][c] += f[v][c];
    }
  }
}

void Dfs(int u, int c) {
  if (f[u][c] == INF) return;                  // 不可达
  for (int v : g[u]) {
    if (g[v].empty()) {                        // 可达的叶子即在最小叶节点集合中
      vis[c][v] = 1;
      continue ;
    }
    if (col[u] == c) {
      if (f[v][c] == f[u][c]) {
        Dfs(v, c);
      }
    } else {
      Dfs(v, c);
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 2, x; i <= n; i++) {
    cin >> x;
    g[x].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    f[i][0] = f[i][1] = g[i].empty() ? 1 : INF;
  }
  dfs(1, 0), dfs(1, 1);
  Dfs(1, 0), Dfs(1, 1);
  for (int i = 1; i <= n; i++) {
    if (vis[0][i] && vis[1][i]) {
      ans ^= i, cnt++;
      if (cnt == 1) {
        cout << i << " ";
      }
    }
  }
  cout << cnt << " " << ans;
  return 0;
}

/*
少年心动是仲夏野草的荒原，割不完，烧不尽。长风一吹，野草遍连了天。

哥……好久不见。

七号路依旧长得没有尽头，梧桐荫还是枝繁叶茂。
人间骄阳正好，风过林梢，彼时他们正当年少。
*/