Luogu

LOJ

分析

可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。

那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。

考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$，这样子 $s$ 到 $t$ 路径上的权值和就是对于 $(s,t)$ 来说满足条件的 $c$ 的数量了。

那么现在只需要统计每两个圆点路径上权值和的和，可以考虑每个点作为 $c$ 的贡献并 DFS 求出。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,m,tot,sumsz,w[N];
vector<int> E[N],T[N];

int dfn[N],low[N],tim=0,sta[N],top=0;
void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u; ++sumsz,w[u]=-1;
    for (int v:E[u]) {
        if (!dfn[v]) {
            tarjan(v),low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                ++tot; w[tot]=1;
                T[tot].emplace_back(u),T[u].emplace_back(tot);
                while (1) {
                    int t=sta[top--]; ++w[tot];
                    T[tot].emplace_back(t),T[t].emplace_back(tot);
                    if (t==v) break;
                }
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int sz[N]; ll ans=0;
void dfs(int u,int fa) {
    sz[u]=u<=n;
    for (int v:T[u]) {
        if (v==fa) continue;
        dfs(v,u);
        ans+=2ll*sz[u]*sz[v]*w[u];
        sz[u]+=sz[v];
    }
    ans+=2ll*sz[u]*(sumsz-sz[u])*w[u];
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read();
        E[u].emplace_back(v),E[v].emplace_back(u);
    }
    tot=n;
    for (int i=1;i<=n;++i)
        if (!dfn[i]) sumsz=0,tarjan(i),dfs(i,0);
    printf("%lld\n",ans);
    return 0;
}