思路
圆方树，一个点双中的所有点都可以被经过，所以给圆点赋值-1，方点赋值为圆点个数，统计圆点两两之间的路径权值和即可
代码
#include#include #include #include using namespace std;int v2[100100*4],fir2[100100*2],nxt2[100100*4],cnt2;void addedge2(int ui,int vi){ ++cnt2; v2[cnt2]=vi; nxt2[cnt2]=fir2[ui]; fir2[ui]=cnt2;}int v[100100*4],fir[100100*2],nxt[100100*4],cnt;void addedge(int ui,int vi){ ++cnt; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt;}int fd_cnt,dfn[100100*2],low[100100*2],w_p[100100*2],dfs_clock;int S[100100*2],topx=0,n,m,num;void dfs(int u){ low[u]=dfn[u]=++dfs_clock; S[++topx]=u; num++; for(int i=fir[u];i;i=nxt[i]){ if(!dfn[v[i]]){ dfs(v[i]); low[u]=min(low[u],low[v[i]]); if(low[v[i]]==dfn[u]){ ++fd_cnt; w_p[fd_cnt]=0; for(int x=0;x!=v[i];topx--){ x=S[topx]; addedge2(fd_cnt,x); addedge2(x,fd_cnt); ++w_p[fd_cnt]; } addedge2(u,fd_cnt); addedge2(fd_cnt,u); ++w_p[fd_cnt]; } } else low[u]=min(low[u],dfn[v[i]]); }}int sz[100100*2];long long ans;void dfs(int u,int f){ sz[u]=(u<=n); for(int i=fir2[u];i;i=nxt2[i]){ if(v2[i]==f) continue; dfs(v2[i],u); ans+=2LL*w_p[u]*sz[u]*sz[v2[i]]; sz[u]+=sz[v2[i]]; } ans+=2LL*w_p[u]*sz[u]*(num-sz[u]); }int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) w_p[i]=-1; for(int i=1;i<=m;i++){ int a,b; scanf("%d %d",&a,&b); addedge(a,b); addedge(b,a); } fd_cnt=n; for(int i=1;i<=n;i++) if(!dfn[i]){ num=0; dfs(i); topx--; dfs(i,0); } printf("%lld\n",ans); return 0;}