P4320

圆方树模板题，统计路径上圆点的个数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 7;
int n, m, q, cnt;
int dfn[N], low[N], stmp;
int f[22][N << 1], val[22][N << 1], dep[N << 1];
vector<int> adj[N], G[N << 1];
stack<int> stk;
void tarjan(int u, int pa, bool first) {
  dfn[u] = low[u] = ++stmp;
  stk.push(u);
  int child = 0;
  for (auto v : adj[u]) {
    if (v == pa) continue;
    if (!dfn[v]) {
      child++;
      tarjan(v, u, false);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        int t;
        ++cnt;
        do {
          t = stk.top();
          stk.pop();
          G[t].emplace_back(n + cnt);
          val[0][t] = 1;
          G[n + cnt].emplace_back(t);
        } while (t != v);
        G[u].emplace_back(n + cnt);
        val[0][u] = 1;
        G[n + cnt].emplace_back(u);
      }
    } else
      low[u] = min(low[u], dfn[v]);
  }
  if (first && child > 1) {
    ++cnt;
    int t;
    do {
      t = stk.top();
      stk.pop();
      G[t].emplace_back(n + cnt);
      val[0][t] = 1;
      G[n + cnt].emplace_back(t);
    } while (t != u);
  }
}
void dfs(int u, int pa, int d) {
  dep[u] = d;
  f[0][u] = pa;
  for (int i = 1; i <= 20; i++) {
    f[i][u] = f[i - 1][f[i - 1][u]];
  }
  for (auto v : G[u]) {
    if (v == pa) continue;
    dfs(v, u, d + 1);
  }
}
int query(int u, int v) {
  int res = 0;
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 20; i >= 0; i--) {
    if (dep[f[i][u]] >= dep[v]) {
      res += val[i][u];
      u = f[i][u];
    }
  }
  if (u == v) return res + val[0][u];
  for (int i = 20; i >= 0; i--) {
    if (f[i][u] != f[i][v]) {
      res += val[i][u] + val[i][v];
      u = f[i][u];
      v = f[i][v];
    }
  }
  res += val[1][u] + val[0][v];
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  int u, v;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  tarjan(1, 1, true);
  dfs(1, 0, 1);
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j <= n + cnt; j++) {
      val[i][j] = val[i - 1][j] + val[i - 1][f[i - 1][j]];
    }    
  }
  cin >> q;
  while (q--) {
    cin >> u >> v;
    cout << query(u, v) << '\n';
  }
  return 0;
}

倍增的做法需要处理一些细节：

val[i][j] 是以 j 点为起点，向上一共 $2^j$ 长度的区间和。

• 细节1: if (u == v) return res + val[0][u];
• 细节2: res += val[1][u] + val[0][v];
• 细节3: dfs(1, 0, 1); 根节点的父亲需要设置为 0，否则会重复累加。

更简单优雅的做法是，在 DFS 的过程中记录到根节点的 dis，查询时返回 dis[u] + dis[v] - 2 * dis[lca] + w[lca] 即可。