题目链接

前置知识

圆方树

解析

考虑一条从\(s\)到\(f\)的路径产生的贡献是除\(s, f\)外经过的点数

如果这条路径经过了某个点双连通分量，点双上的每个点都会产生贡献

点双\(\rightarrow\)圆方树

建出圆方树，方点权值为代表的点双的大小

这样两点间的路径对应成两个圆点间的路径，由于一条路径会经过\(s\)和\(f\)自己所在的点双，而\(c\)不能在\(s\)和\(f\)，所以每个圆点权值为\(-1\)

于是一对\(s, f\)的贡献就是圆方树上的路径上的点权和

考虑每个点被多少条路径经过，乘上点权就是这个点对答案的贡献

于是就变成了一个简单的树上路径统计问题

因为交换\(s\)和\(f\)算不同的方案，最后答案乘\(2\)

代码

自带大常数……洛谷\(1000ms\)，\(LOJ \ 5600ms\)……

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAXN 100005#define MAXM 200005typedef long long LL;struct Graph {    struct Edge {        int v, next;        Edge(int _v = 0, int _n = 0):v(_v), next(_n) {}    } edge[MAXM << 1];    int head[MAXN << 1], cnt;    void init() { memset(head, -1, sizeof head); cnt = 0; }    void add_edge(int u, int v) { edge[cnt] = Edge(v, head[u]); head[u] = cnt++; }    void insert(int u, int v) { add_edge(u, v); add_edge(v, u); }};void Tarjan(int, int);void dfs(int, int);int N, M, dfn[MAXN], low[MAXN], idx, tot;int stk[MAXN], top;int size[MAXN << 1], w[MAXN << 1], root[MAXN << 1];bool vis[MAXN << 1];LL ans;Graph G, T;int main() {    scanf("%d%d", &N, &M);    tot = N;    G.init(); T.init();    for (int i = 0; i < M; ++i) {        int u, v; scanf("%d%d", &u, &v);        G.insert(u, v);    }    for (int i = 1; i <= N; ++i) {        w[i] = -1, size[i] = 1;        if (!dfn[i]) Tarjan(i, 0);    }    for (int i = 1; i <= tot; ++i)        if (!vis[i]) {            root[i] = i;            dfs(i, 0);        }    for (int i = 1; i <= tot; ++i) ans += (LL)(size[root[i]] - size[i]) * size[i] * w[i];    printf("%lld\n", ans << 1);    return 0;}void Tarjan(int u, int fa) {    dfn[u] = low[u] = ++idx;    for (int i = G.head[u]; ~i; i = G.edge[i].next) {        int v = G.edge[i].v;        if (v == fa) continue;        if (!dfn[v]) {            stk[top++] = v;            Tarjan(v, u);            low[u] = std::min(low[u], low[v]);            if (low[v] >= dfn[u]) {                int p; ++tot;                do {                    p = stk[--top];                    T.insert(tot, p);                    ++w[tot];                } while(p ^ v);                T.insert(tot, u);                ++w[tot];            }        } else low[u] = std::min(low[u], dfn[v]);    }}void dfs(int u, int fa) {    vis[u] = 1;    for (int i = T.head[u]; ~i; i = T.edge[i].next) {        int v = T.edge[i].v;        if (v == fa) continue;        root[v] = root[u], dfs(v, u);        ans += (LL)size[v] * size[u] * w[u];        size[u] += size[v];    }}//Rhein_E