【资料图】
题目链接
先观察满足题目中给出的限制的图有什么特点。先看\(C_u\)，它指的是所有与\(u\)在同一个简单环内的节点。发现一个点v在\(C_u\)中，当且仅当\(u,v\)点双连通。关于点双连通的判断。首先必要性是显然的，不点双连通显然不行。至于充分性，可以把\(u\)作为根跑出dfs树，根据上面点双连通的判断方法，此时u和v之间的树上路径中的每一个点一定至少有1条非树边"跨过"(除了u和v)。至于跨过的定义，下图中左边的红点被跨过了，而右边的没有。
然后，u和v在一个简单环中等价于：以u为原点、v为汇点，每条边能双向走、容量为1，此时u到v的最大流\(\ge 2\)。由于最大流等于最小割，证明最小割\(\ge 2\)即可。很容易发现不可能只割掉1条边使uv不连通，所以原命题得证。
那么\(S_u=C_u\)又说明什么呢？再来看看上面链接里判断点双连通的方法，其中有些树边被加进了同一个连通块中，不妨看成把一些树边染成了相同的颜色，没有非树边跨过的边没有被染颜色，则所有同色边连接的所有点是属于同一个点双连通分量的。这题中\(S_u=C_u\)其实说明了不能有一个点同时属于两个点双连通分量，也就是不能有两条都被染色但颜色不同的树边挨在一起。如果一个点u同时属于两个分量，那显然这两个分量中所有的点都在\(C_u\)中，但无法找到一个很长的简单环同时包括这两个分量的所有点。所以这就说明了输入的图长这样：一些由同色边连成的点双连通分量，之间用树边(同时也是桥边)连成一棵树。在这种情况下，点双分量和边双分量是一样的，边双比较好写，所以可以用边双的方法来把所有分量处理出来。
现在处理出所有的分量了，来看回答询问。首先u和v之间的原图桥边肯定是不能删的。把每个分量看成一个点建一棵新树，令U表示u所在的分量缩成的点，V同理。则U~V路径上某一些点代表的分量中的所有边能被删掉。对于路径中间一个不是U也不是V的点，它代表的分量中的边能被删取决于：
对于端点U和V的分量来说也是一样的，但是需要分类讨论。统计答案维护每个点到根的和就行了，询问的时候求一下LCA，然后相减。维护的时候细节比较多，但是都不难想。
时间复杂度\(O(nlogn)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;int n,m,add[200010],dep[200010];vector e,g[200010],tg[200010];bool vis[200010],isBri[200010];void dfs(int pos,int par){ vis[pos]=true; rep(i,g[pos].size()) if(g[pos][i].fi!=par) { if(!vis[g[pos][i].fi]) tg[pos].pb(g[pos][i]),dep[g[pos][i].fi]=dep[pos]+1,dfs(g[pos][i].fi,pos); else if(dep[g[pos][i].fi]-1) isBri[lst]=true;}int fa[200010],ecnt[200010];vector v[200010];int Find(int x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}vector > ng[200010];int root,dep2[200010],fa2[200010][23],sum[200010];map consum;pii fae[200010];void dfs3(int pos,int par,int dd,int becon=-1){ dep2[pos]=dd;fa2[pos][0]=par; rep(i,ng[pos].size()) if(ng[pos][i].fi!=par) { sum[ng[pos][i].fi]=sum[pos]; if(becon!=-1&&becon!=ng[pos][i].se.fi) sum[ng[pos][i].fi]+=ecnt[pos]; dfs3(ng[pos][i].fi,pos,dd+1,ng[pos][i].se.se); } else fae[pos]=ng[pos][i].se;}int getLCA(int x,int y){ for(int i=19;i>=0;--i) if(fa2[x][i]>0&&dep2[fa2[x][i]]>=dep2[y]) x=fa2[x][i]; for(int i=19;i>=0;--i) if(fa2[y][i]>0&&dep2[fa2[y][i]]>=dep2[x]) y=fa2[y][i]; if(x==y) return x; for(int i=19;i>=0;--i) if(fa2[x][i]!=fa2[y][i]) x=fa2[x][i],y=fa2[y][i]; return fa2[x][0];}int getFa(int x,int y){ for(int i=19;i>=0;--i) if(y&(1<>n>>m; int x,y; rep(i,m) { scanf("%d%d",&x,&y); g[x].pb(mpr(y,i));g[y].pb(mpr(x,i)); e.pb(mpr(x,y)); } dfs(1,0); dfs2(1); repn(i,n) fa[i]=i; rep(i,m) if(!isBri[i]) { ++ecnt[e[i].fi];++ecnt[e[i].se]; if(Find(e[i].fi)!=Find(e[i].se)) fa[Find(e[i].fi)]=Find(e[i].se); } repn(i,n) v[Find(i)].pb(i); repn(i,n) if(v[i].size()) rep(j,v[i].size()) if(v[i][j]!=i) ecnt[i]+=ecnt[v[i][j]]; rep(i,m) if(isBri[i]) { x=Find(e[i].fi);y=Find(e[i].se); ng[x].pb(mpr(y,e[i]));ng[y].pb(mpr(x,mpr(e[i].se,e[i].fi))); consum[mpr(x,y)]=consum[mpr(y,x)]=e[i].fi+e[i].se; } root=Find(1); dfs3(root,0,0); rep(i,20) repn(j,n) fa2[j][i+1]=fa2[fa2[j][i]][i]; int q; cin>>q; rep(qn,q) { scanf("%d%d",&x,&y); if(x==y) { puts("0"); continue; } int xx=x,yy=y; x=Find(x);y=Find(y); if(x==y) { printf("%d\n",ecnt[x]/2); continue; } if(dep2[x]>dep2[y]) swap(x,y),swap(xx,yy); int lca=getLCA(x,y); if(lca==x) { int nlca=getFa(y,dep2[y]-dep2[x]-1); int ans=sum[y]-sum[nlca]; if(fae[y].fi!=yy) ans+=ecnt[y]; if(fae[nlca].se!=xx) ans+=ecnt[x]; printf("%d\n",ans/2); } else { int xlca=getFa(x,dep2[x]-dep2[lca]-1),ylca=getFa(y,dep2[y]-dep2[lca]-1); int ans=sum[x]+sum[y]-sum[xlca]-sum[ylca]; if(fae[xlca].se!=fae[ylca].se) ans+=ecnt[lca]; if(fae[x].fi!=xx) ans+=ecnt[x]; if(fae[y].fi!=yy) ans+=ecnt[y]; printf("%d\n",ans/2); } } termin();} 
