先观察满足题目中给出的限制的图有什么特点。先看\(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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void 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 <pii> 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]<dep[pos])
{
++add[pos];
--add[g[pos][i].fi];
}
}
}
void dfs2(int pos,int lst=-1)
{
rep(i,tg[pos].size())
{
dfs2(tg[pos][i].fi,tg[pos][i].se);
add[pos]+=add[tg[pos][i].fi];
}
if(add[pos]==0&&lst>-1) isBri[lst]=true;
}
int fa[200010],ecnt[200010];
vector <int> v[200010];
int Find(int x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}
vector <pair <int,pii> > ng[200010];
int root,dep2[200010],fa2[200010][23],sum[200010];
map <pii,int> 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<<i)) x=fa2[x][i];
return x;
}
int main()
{
fileio();
cin>>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();
}