[洛谷P5966] [BZOJ4344] [POI2016] Hydrorozgrywka

JCY_ · 2023-11-28 14:40:19 · 题解

更好的阅读体验

题解

建出原图的圆方树。由于原图无重边，不妨把桥看作二元环建树，这样圆点只与方点直接相连。

圆方树定某一圆点为根后，若点 u 是圆点，定义点 u 的子仙人掌为点 u 子树中的圆点在原图的导出子图，定义该子仙人掌的根为点 u；若点 u 是方点，定义点 u 的子仙人掌为点 u 子树中的圆点和点 u 的父亲在原图的导出子图，定义该子仙人掌的根为点 u 的父亲。

考虑如何判断棋子在点 x 是否先手必胜。在圆方树上定圆点点 x 为根，手玩发现上文的「子仙人掌」结构是重要的：子仙人掌的包含关系呈树形，因此玩家只能在子仙人掌的根处选择是否进入。

这启发我们在圆方树上进行关于子树（即子仙人掌）信息的树形 dp。

在一切的之前先想象一下圆方树上 dp 的过程：方点的转移是合并若干个根节点串成环的子仙人掌的信息，圆点的转移是合并若干个共且仅共根节点的子仙人掌的信息。

设计 dp 状态

最直接的设计 dp 状态的方法是 f_u = 0 / 1 表示只考虑点 u 的子仙人掌，棋子在其根先手必败 / 先手必胜。不难发现这种状态设计把「棋子最终停留在子仙人掌的根」看作失败，但由于我们上述状态设计中只考虑点 u 的子仙人掌，实际上棋子最终停留在子仙人掌的根后还可能进入其他子仙人掌进行游戏。这一缺陷导致该 dp 状态设计无法准确进行「进入一个子仙人掌然后出来」这种转移。

我们想象子仙人掌的根节点向外部连出一条边。

如果先手必败，那么先手会直接走那条边。
如果先手必胜并且可以逼迫后手最终停留在非根节点，先手会进行这个必胜的游戏。
否则，先手可以直接选择走那条边，也可以选择逼迫后手走那条边。

我们把这三种情况分别对应 f_u = 0 / 1 / 2。

进行 dp 转移

下文中点 v 代表点 u 的某一个儿子。

方点

如果点 u 只有一个儿子，则它代表了一条桥边。此时必有 f_u \neq 2，因此 f_u \leftarrow [f_v = 0]。

否则，考虑在环上按照某个方向走一圈的过程：

如果我们碰上了一个 f_v = 0 的仙人掌，当前玩家必然会忽略它。

如果我们碰上了一个 f_v = 1 的仙人掌，当前玩家必胜。

如果我们碰上了一个 f_v = 2 的仙人掌，当前玩家可以选择是否改变先后手，因此当前玩家必胜。

任何一个公平组合游戏中，如果你能在某一时刻有两种进入完全相同的局面、但先后手不同的决策，那么你是必胜的（这里的决策相当于把有向图上的很多已经确定会走的步打包成一步）。

因此找到环上向左走和向右走遇到的第一个 f_v \neq 0 的 v，根据走的距离的奇偶性分别判断是否必胜即可。二者中有至少一者必胜则 f_u \leftarrow 1，否则 f_u \leftarrow 0。

特殊情况是 \forall v, f_v = 0，这种情况下只能绕着环走一圈。如果环是奇环则 f_u \leftarrow 2，否则 f_u \leftarrow 0。

圆点

如果 \exists v, f_v = 1，则 f_u \leftarrow 1。这是因为当前玩家肯定会选择进入这个子仙人掌。

否则，如果 2 \nmid \sum_v [f_v = 2] 则 f_u \leftarrow 2，反之 f_u \leftarrow 0。这是因为 2 \nmid \sum_v [f_v = 2] 时如果先手选择先改变一次先后手，在这之后每当后手通过一棵 f_v = 2 的子仙人掌改变了先后手，先手总能通过另一棵改变回去。

换根

综上，我们容易得到一个 O(n^2) 的算法，上述过程容易换根 dp 做到 O(n)。

2025.7.19 修正代码换根 dp 部分的错误实现

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
constexpr int MAXN = 5e5 + 10;
int n, dfn[MAXN], low[MAXN], dfc, stk[MAXN], tp, num, dwn[MAXN * 2];
int cnt1[MAXN], cnt2[MAXN], up[MAXN * 2], all[MAXN], posl[MAXN * 2],
    posr[MAXN * 2];
vector<int> og[MAXN], g[MAXN * 2];
void tarjan(int u) {
  dfn[u] = low[u] = ++dfc;
  stk[++tp] = u;
  for (auto v : og[u]) {
    if (!dfn[v]) {
      tarjan(v);
      chkmin(low[u], low[v]);
      if (low[v] == dfn[u]) {
        g[u].emplace_back(++num);
        while (true) {
          int t = stk[tp--];
          g[num].emplace_back(t);
          if (t == v) break;
        }
      }
    } else {
      chkmin(low[u], dfn[v]);
    }
  }
}
void dfs1(int u) {
  for (auto v : g[u]) dfs1(v);
  if (u <= n) {
    for (auto v : g[u]) {
      if (dwn[v] == 1) {
        ++cnt1[u];
      } else if (dwn[v] == 2) {
        ++cnt2[u];
      }
    }
    if (cnt1[u]) {
      dwn[u] = 1;
    } else {
      dwn[u] = (cnt2[u] & 1 ? 2 : 0);
    }
  } else {
    if (g[u].size() == 1) {
      dwn[u] = !dwn[g[u][0]];
    } else {
      posl[u] =
          find_if(g[u].begin(), g[u].end(), [](int x) { return dwn[x]; }) -
          g[u].begin();
      if (posl[u] == (int)g[u].size()) {
        dwn[u] = (g[u].size() & 1 ? 0 : 2);
      } else {
        posr[u] =
            find_if(g[u].rbegin(), g[u].rend(), [](int x) { return dwn[x]; }) -
            g[u].rbegin();
        dwn[u] = (posl[u] & 1) || (posr[u] & 1);
      }
    }
  }
}
void dfs2(int u) {
  if (u <= n) {
    if (cnt1[u] + (up[u] == 1)) {
      all[u] = 1;
    } else {
      all[u] = ((cnt2[u] + (up[u] == 2)) & 1 ? 2 : 0);
    }
    for (auto v : g[u]) {
      if (cnt1[u] + (up[u] == 1) - (dwn[v] == 1)) {
        up[v] = 1;
      } else {
        up[v] = ((cnt2[u] + (up[u] == 2) - (dwn[v] == 2)) & 1 ? 2 : 0);
      }
      dfs2(v);
    }
  } else {
    if (g[u].size() == 1) {
      up[g[u][0]] = !up[u];
      dfs2(g[u][0]);
    } else {
      static int nxt[MAXN];
      for (int i = g[u].size() - 1, lst = g[u].size(); i >= 0; --i) {
        nxt[i] = lst;
        if (dwn[g[u][i]]) lst = i;
      }
      if (up[u]) posl[u] = -1;
      for (int i = 0, v, lst = (up[u] ? -1 : -2); i < (int)g[u].size(); ++i) {
        v = g[u][i];
        if (lst == -2 && nxt[i] == (int)g[u].size()) {
          up[v] = (g[u].size() & 1 ? 0 : 2);
        } else if (lst == -2) {
          up[v] = !((i + posr[u]) & 1) || !((nxt[i] - i) & 1);
        } else if (nxt[i] == (int)g[u].size()) {
          up[v] = !((i - lst) & 1) || ((g[u].size() - i + posl[u]) & 1);
        } else {
          up[v] = !((i - lst) & 1) || !((nxt[i] - i) & 1);
        }
        if (dwn[v]) lst = i;
      }
      for (auto v : g[u]) dfs2(v);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int m;
  cin >> n >> m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    og[u].emplace_back(v);
    og[v].emplace_back(u);
  }
  num = n;
  tarjan(1);
  dfs1(1);
  dfs2(1);
  for (int i = 1; i <= n; ++i) cout << 2 - (bool)all[i] << "\n";
  return 0;
}
/*
g++ Hydro.cpp -o Hydro -std=c++14 -O2 -Wall -Wextra -Wshadow -g
-fsanitize=address,undefined
*/