RT,参考第一篇题解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+50;
ll n,m,cnt,idx;
ll dfn[N],low[N],st[N],tp,num[N],tot,ans,siz[N];
struct Node{
ll to[N*2],nex[N*2],la[N],mcnt=1;
void add(ll u,ll v){
mcnt++;
nex[mcnt]=la[u],to[mcnt]=v;
la[u]=mcnt;
}
}a,b;
void tarjan(ll x,ll lst){
dfn[x]=low[x]=++cnt;
num[x]=-1;
st[++tp]=x;
tot++;
for(ll i=a.la[x];i;i=a.nex[i]){
if(lst==(i^1))continue;
ll to=a.to[i];
if(!dfn[to]){
tarjan(to,i);
low[x]=min(low[x],low[to]);
if(dfn[x]<=low[to]){
ll v;idx++;num[idx]++;
b.add(idx,x);b.add(x,idx);
do v=st[tp--],num[idx]++,b.add(idx,to),b.add(to,idx);while(v!=to);
}
}
else low[x]=min(low[x],dfn[to]);
}
}
void dfs(ll x,ll fa){
siz[x]=x<=n;
for(ll i=b.la[x];i;i=b.nex[i]){
ll to=b.to[i];
if(to==fa)continue;
dfs(to,x);
ans+=2ll*siz[x]*siz[to]*num[x];
siz[x]+=siz[to];
}
ans+=2ll*siz[x]*(tot-siz[x])*num[x];
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1,u,v;i<=m;i++){
scanf("%lld%lld",&u,&v);
a.add(u,v);a.add(v,u);
}
idx=n;
for(ll i=1;i<=n;i++){
if(!dfn[i]){
tot=tp=0;
tarjan(i,-1);
dfs(i,0);
}
}
printf("%lld",ans);
return 0;
}