「APIO2018」铁人两项

知识点：圆方树，树形 DP

原题面：Loj、Luogu。

简述

给定一 \(n\) 个节点 \(m\) 条边的无向图，求存在多少对有序三元组 \((s,c,f)\)，满足 \(s,c,f\) 互不相同且存在一条从 \(s\) 到 \(f\) 的简单路径使得 \(c\) 在路径上出现。
\(1\le n\le 10^5\)，\(1\le m\le 2\times 10^5\)。
1S，1G。

分析

圆方树相关知识详见：。

点双存在一个性质：对于点数 \(\ge 3\) 的点双中任意两个不同的点之间，一定存在一条简单路径经过在同一点双内的任意一点。正确性可以通过点双的定义感性理解，一种严谨的证明详见 OI-Wiki 上该题题解。

于是可以考虑建出原图的圆方树。考虑圆方树上任意两个圆点 \(x,y\) 之间的路径上的点：对于路径上某圆点 \(z\)，显然原图中 \(z\) 一定在 \(x\) 到 \(y\) 的一条简单路径上，三元组 \((x,z,y)\) 对答案有贡献。对于路径上某方点，根据上述性质，方点所对应的点双中的所有节点也一定可以出现在 \(x\) 到 \(y\) 的一条简单路径上。
则对于圆方树上任意两圆点 \(s,f\)，能与它们组成合法有序三元组的 \(c\) 即为圆方树上两点路径上圆点与方点维护的所有圆点并集的大小减 2（不包含 \(s,f\)）。考虑到圆方树上圆点只与方点相连，方点只与圆点相连，路径上的圆点一定被路径上它们相邻的方点维护，考虑给各点赋值来方便统计。

考虑令方点权值变为代表的点双的大小，圆点的权值为 \(-1\)。圆方树上任意两圆点对答案的贡献即为路径上点权之和。问题变为统计树上所有以圆点为端点路径权值之和。转化为每个点被多少路径所包括，简单树形 DP 即可。总时间复杂度 \(O(n)\) 级别。

注意原图可能不连通。

代码中并没有显式的 DP 数组。

代码

//知识点：圆方树
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, e_num, val[kN], head[kN], v[kN << 1], ne[kN << 1];
int sumsz, dfnnum, cnt, dfn[kN], low[kN];
std::vector  newv[kN];
std::stack  st;
LL ans;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Add(int u_, int v_) {
  v[++ e_num] = v_, ne[e_num] = head[u_], head[u_] = e_num;
}
void Tarjan(int u_) {
  dfn[u_] = low[u_] = ++ dfnnum;
  st.push(u_);
  ++ sumsz;

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (!dfn[v_]) {
      Tarjan(v_);
      Chkmin(low[u_], low[v_]);
      if (low[v_] >= dfn[u_]) {
        val[++ cnt] = 1;
        newv[cnt].push_back(u_), newv[u_].push_back(cnt);
        while (true) {
          int top_ = st.top();
          ++ val[cnt];
          newv[cnt].push_back(top_), newv[top_].push_back(cnt);
          st.pop();
          if (top_ == v_) break; //特 别 注 意
          //u_ 与 v_ 在栈中可能不相邻，停止条件必须要写成这样
        }
      }
    } else {
      Chkmin(low[u_], dfn[v_]);
    }
  }
}
int Dfs(int u_, int fa_) {
  int sz = u_ <= n;
  for (int i = 0, lim = newv[u_].size(); i < lim; ++ i) {
    int v_ = newv[u_][i];
    if (v_ == fa_) continue ;
    int ret = Dfs(v_, u_);
    ans += 2ll * sz * ret * val[u_]; //子树内的点经过 u_ 构成的路径
    sz += ret;
  }
  ans += 2ll * sz * (sumsz - sz) * val[u_]; //子树内的点与子树外的点构成的路径
  return sz;
}
//=============================================================
int main() { 
  cnt = n = read(), m = read();
  for (int i = 1; i <= n; ++ i) val[i] = -1;
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  for (int i = 1; i <= n; ++ i) { //注意原图可能不连通
    if (dfn[i]) continue ;
    sumsz = 0;
    Tarjan(i); Dfs(i, 0);
  }
  printf("%lld\n", ans);
  return 0; 
}