是不是只有我以为这是最小割树裸题 然后SB地大力分治跑最小割
因为一个点度数不超过3 那么答案就是 0 1 2 3 先不在一个连通块的是0 在一个连通块但不在同一个边双里的是1
然后怎么分辨 2 和 3 为2当且仅当存在删去某一条边 两个点不在同一个点双里 为3 也就是两个点所在的点双完全一样 我们尝试删除每条边 然后hash一下就好了
#include<cstdio> #include<cstdlib> #include<algorithm> #include<stack> #include<cstring> using namespace std; typedef unsigned long long ull; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=3005; const int M=4505; struct edge{ int u,v,next; }G[M<<1]; int vst[M<<1]; int head[N],inum=1; inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p; } int n,m; stack<int> sta; int pre[N],low[N],clk; ull bcc[N],S=10007; int cnt; int cur,rt[N]; #define V G[p].v inline void dfs(int u,int fa){ rt[u]=cur; pre[u]=low[u]=++clk; sta.push(u); for (int p=head[u];p;p=G[p].next) if (!vst[p] && p!=(fa^1)){ if (!pre[V]){ dfs(V,p); low[u]=min(low[u],low[V]); if (low[V]>pre[u]){ ++cnt; int t; while (sta.top()!=V) t=sta.top(),sta.pop(),bcc[t]=bcc[t]*S+cnt; t=sta.top(),sta.pop(),bcc[t]=bcc[t]*S+cnt; } }else low[u]=min(low[u],pre[V]); } } inline void BCC(){ clk=cnt=0; for (int i=1;i<=n;i++) pre[i]=low[i]=0; for (int i=1;i<=n;i++) if (!pre[i]){ cur=i; dfs(i,0); ++cnt; int t; while (!sta.empty()) t=sta.top(),sta.pop(),bcc[t]=bcc[t]*S+cnt; } } int ans[N][N]; int main(){ int iu,iv; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=1;i<=m;i++) read(iu),read(iv),add(iu,iv,++inum),add(iv,iu,++inum); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) ans[i][j]=-1; BCC(); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (rt[i]^rt[j]) ans[i][j]=0; else if (bcc[i]!=bcc[j]) ans[i][j]=1; for (int i=1;i<=n;i++) bcc[i]=0; for (int i=2;i<=inum;i+=2){ vst[i]=vst[i^1]=1; BCC(); vst[i]=vst[i^1]=0; } for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (ans[i][j]==-1) if (bcc[i]==bcc[j]) ans[i][j]=3; else ans[i][j]=2; int Ans=0; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) Ans+=ans[i][j]; printf("%d\n",Ans); return 0; }