题解 QOJ837 / ZROI1287【Giant Penguin】

Petrozavodsk Winter 2020. Day 3. 300iq Contest 3. Problem G. Giant Penguin

Giant Penguin - Problem - QOJ.ac

题目描述

有一个 \(n\) 个点 \(m\) 条边的连通无向无权图，满足每个节点在至多 \(k\) 个简单环上（没有重复顶点的环是简单环）。\(q\) 次操作支持：1. 标记一个点； 2. 询问一个点到任意标记点的最短距离。

\(n, q\leq 1\times 10^5, m\leq 2n, k\leq 10\)。

solution

本题难点在于发现这是一道点分治题。

考虑任选一个节点 \(rt\)，以它为根搜一棵 dfs 生成树。因为每个节点在至多 \(k\) 个简单环上，所以至多有 \(k\) 条返祖边（dfs 生成树没有横叉边），这是关键所在。考虑将这 \(k\) 条返祖边拿出来，以 \(k\) 条边各自任意的一个端点为关键点，那么图上两个点之间的最短路要么经过 \(k\) 个关键点，要么经过根，要么不走返祖边和根，第三者可以通过点分治使其成为子问题。然后根据自己的喜好写点分治或者点分树即可 \(O(nk\log n)\) 解决该问题。

以上省略的部分细节：

1. 如果 dfs 生成树的根不为分治中心（这是大多数情况），那么会出现横叉边，只有连接由分治中心分割的两棵不同子树的横叉边需要在这层分治中处理。
2. 点分树做法需要存储当前分治层的关键点到其它点的最短路。可以记录当前分治深度，同一深度的分治问题互不相交，可以存到同一个数组中，而分治深度显然不超过 \(O(\log n)\)（注意求重心要传入正确的子树大小以防深度超过 \(\log_2 n\)）。当然离线点分治不会有这个问题。

code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, m, anc[100010], siz[100010], smx[100010], td[100010], tf[100010];
bool cut[100010];
vector<int> g[100010];
void dfs(int u, int fa) {/*{{{*/
  anc[u] = fa;
  for (int v : g[u]) if (!anc[v]) debug("%d -- %d\n", u, v), dfs(v, u);
}/*}}}*/
bool ontree(int u, int v) {/*{{{*/
  return anc[u] == v || anc[v] == u;
}/*}}}*/
int findcen(int u, int fa, int T) {/*{{{*/
  siz[u] = 1, smx[u] = 0;
  int rt = -1;
  for (int v : g[u]) if (!cut[v] && v != fa && ontree(u, v)) {
    int rs = findcen(v, u, T);
    if (rt == -1 || smx[rs] < smx[rt]) rt = rs;
    siz[u] += siz[v], smx[u] = max(smx[u], siz[v]);
  }
  smx[u] = max(smx[u], T - siz[u]);
  return rt == -1 || smx[u] < smx[rt] ? u : rt;
}/*}}}*/
int dis[100010][20][21], ans[100010][21], cnt[100010];
int vis[100010], tim, col[100010];
void bfs(int st, int dep, int id) {/*{{{*/
  queue<int> q;
  q.push(st);
  dis[st][dep][id] = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) if (vis[v] == tim && dis[v][dep][id] > dis[u][dep][id] + 1) {
      dis[v][dep][id] = dis[u][dep][id] + 1;
      q.push(v);
    }
  }
}/*}}}*/
void solve(int rt, int fa) {
  int dep = td[rt] = td[fa] + 1;
  assert(dep < 20);
  tf[rt] = fa;
  queue<int> q;
  vis[rt] = ++tim;
  col[rt] = -1;
  for (int v : g[rt]) if (!cut[v] && ontree(rt, v)) col[v] = v, q.push(v);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = tim;
    for (int v : g[u]) if (!cut[v] && vis[v] != tim && ontree(u, v)) q.push(v), col[v] = col[u];
  }
  q.push(rt);
  vis[rt] = ++tim;
  vector<int> key{rt};
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) if (!cut[v]) {
      if (ontree(u, v)) { if (vis[v] == tim - 1) q.push(v), vis[v] = tim; }
      else if (vis[v] >= tim - 1 && col[u] != col[v]) key.push_back(u), key.push_back(v);
    }
  }
  {
    auto b = key.begin(), e = key.end();
    sort(b, e), key.erase(unique(b, e), e);
  }
  cnt[rt] = key.size();
  assert(cnt[rt] <= 21);
  debug("rt = %d\n", rt);
  for (int i = 0; i < cnt[rt]; i++) assert(vis[key[i]] == tim), bfs(key[i], dep, i), debug("key[%d] = %d\n", i, key[i]);
  cut[rt] = true;
  for (int v : g[rt]) if (!cut[v] && ontree(rt, v)) {
    findcen(v, rt, siz[v]);
    solve(findcen(v, rt, siz[v]), rt);
  }
}
void mdf(int u) {
  for (int p = u; p; p = tf[p]) {
    for (int i = 0; i < cnt[p]; i++) ans[p][i] = min(ans[p][i], dis[u][td[p]][i]);
  }
}
int qry(int u) {
  int res = 1e9;
  for (int p = u; p; p = tf[p]) {
    for (int i = 0; i < cnt[p]; i++) res = min(res, ans[p][i] + dis[u][td[p]][i]);
  }
  return res;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  memset(dis, 0x3f, sizeof dis);
  memset(ans, 0x3f, sizeof ans);
  int q, op, x;
  cin >> n >> m >> q;
  for (int i = 1, u, v; i <= m; i++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
  dfs(1, -1);
  td[0] = -1;
  solve(findcen(1, 0, n), 0);
  cin >> q;
  while (q--) {
    cin >> op >> x;
    if (op == 1) mdf(x);
    else cout << qry(x) << endl;
  }
  return 0;
}