题面
https://www.luogu.org/problem/P4630
题解
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #define ri register int #define LL long long #define N 200500 #define M 250000 using namespace std; inline int read() { int f=0,ret=0; char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&& ch<='9') ret=ret*10+(ch-'0'),ch=getchar(); return f?-ret:ret; } int n,m,tn; LL ans=0; struct tree { vector<int> to[N]; LL s1[N],s2[N]; LL siz[N]; void add_edge(int a,int b) { //printf("%d %d ",a,b); to[a].push_back(b); to[b].push_back(a); } void tonji(int x,int ff,int &tot) { if (x<=tn) tot++; for (ri i=0;i<to[x].size();i++) { int y=to[x][i]; if (y==ff) continue; tonji(y,x,tot); } } void dp(int x,int ff,int pa,int tot) { siz[x]=(x<=tn); for (ri i=0;i<to[x].size();i++) { if (to[x][i]==ff) continue; dp(to[x][i],x,pa,tot); siz[x]+=siz[to[x][i]]; } if (x>tn) { s1[x]=0LL; s2[x]=0LL; for (ri i=0;i<to[x].size();i++) { if (to[x][i]==ff) continue; s1[x]+=siz[to[x][i]]; s2[x]+=siz[to[x][i]]*siz[to[x][i]]; } s1[x]+=(tot-siz[x]); s2[x]+=(tot-siz[x])*(tot-siz[x]); } } void getans(int x,int ff,int pa) { for (ri i=0;i<to[x].size();i++) { int y=to[x][i]; if (y==ff) continue; getans(y,x,pa); } if (x<=tn) { s1[x]=0LL; s2[x]=0LL; for (ri i=0;i<to[x].size();i++) { s1[x]+=s1[to[x][i]]; s2[x]+=s2[to[x][i]]; } for (ri i=0;i<to[x].size();i++) { if (to[x][i]==ff) continue; s1[x]-=(siz[pa]-siz[to[x][i]]); s2[x]-=(siz[pa]-siz[to[x][i]])*(siz[pa]-siz[to[x][i]]); } if (x!=pa) { s1[x]-=siz[x]; s2[x]-=siz[x]*siz[x]; } ans+=(s1[x]*s1[x]-s2[x])/2; } } } T; struct graph { vector<int> to[N]; int clo,top; int dfn[N],low[N]; int S[N]; void add_edge(int u,int v) { to[u].push_back(v); to[v].push_back(u); } void tarjan(int x) { dfn[x]=low[x]=++clo; S[++top]=x; for (ri i=0;i<to[x].size();i++) { int y=to[x][i]; if (dfn[y]) { low[x]=min(low[x],dfn[y]); } else { tarjan(y); low[x]=min(low[x],low[y]); if (low[y]>=dfn[x]) { ++n; T.add_edge(x,n); int t; do { t=S[top--]; T.add_edge(t,n); } while (t!=y); } } } } } G; int main(){ tn=n=read(); m=read(); for (ri i=1;i<=m;i++) { int u=read(),v=read(); G.add_edge(u,v); } for (ri i=1;i<=tn;i++) if (!G.dfn[i]) { G.tarjan(i); int tot=0; T.tonji(i,i,tot); T.dp(i,i,i,tot); T.getans(i,i,i); } printf("%lld ",ans*2); }