题面

\(LOJ\)自己找。。

Sol

建立圆方树

考虑枚举起点\(s\)和终点\(t\)

那么答案就是\(s\)到\(t\)间的点双的点数和减去\(s,t\)

设方点权值为点双的点数，圆点的权值为\(-1\)

那么就是求\(s,t\)的路径上的点权和

现在考虑中间的点\(x\)

那么它的贡献就是经过它的路径的条数*它的权值

树\(DP\)得解

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(4e5 + 5);int n, m, dfn[maxn], low[maxn], idx, sum;int sta[maxn], top, tot, val[maxn], size[maxn];ll ans;struct Edge{    int first[maxn], cnt, nxt[maxn << 1], to[maxn << 1];    IL void Init(){        cnt = 0, Fill(first, -1);    }    IL void Add(RG int u, RG int v){        nxt[cnt] = first[u], to[cnt] = v, first[u] = cnt++;    }} e1, e2;IL void Tarjan(RG int u){    dfn[u] = low[u] = ++idx, sta[++top] = u, size[u] = 1;    for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){        RG int v = e1.to[e];        if(!dfn[v]){            Tarjan(v), low[u] = min(low[u], low[v]);            if(low[v] >= dfn[u]){                RG int x = 0, num = 1; ++tot;                do{                    x = sta[top--], ++num;                    e2.Add(tot, x), e2.Add(x, tot);                    size[tot] += size[x];                } while(x != v);                val[tot] = num, size[u] += size[tot];                e2.Add(tot, u), e2.Add(u, tot);            }        }        else low[u] = min(low[u], dfn[v]);    }}IL void Dfs(RG int u, RG int ff){    RG int tmp = u <= n;    ans += 2LL * size[u] * (sum - size[u]) * val[u];    for(RG int e = e2.first[u]; e != -1; e = e2.nxt[e]){        RG int v = e2.to[e];        if(v != ff){            ans += 2LL * tmp * size[v] * val[u];            tmp += size[v];            Dfs(v, u);        }    }}int main(){    e1.Init(), e2.Init();    tot = n = Input(), m = Input();    for(RG int i = 1; i <= n; ++i) val[i] = -1;    for(RG int i = 1; i <= m; ++i){        RG int u = Input(), v = Input();        e1.Add(u, v), e1.Add(v, u);    }    for(RG int i = 1; i <= n; ++i)        if(!dfn[i]) Tarjan(i), sum = size[i], Dfs(i, 0);    printf("%lld\n", ans);    return 0;}