题目描述
C 国是一个繁荣昌盛的国家，它由 \(n\) 座城市和 \(m\) 条有向道路组成，城市从 \(1\) 到 \(n\) 编号。如果从 \(x\) 号城市出发，经过若干条道路后能到达 \(y\) 号城市，那么我们称 \(x\) 号城市可到达 \(y\) 号城市，记作 \(x\Rightarrow y\)。C 国的道路有一个特点：对于三座城市 \(x\)，\(y\)，\(z\)，若 \(x\Rightarrow z\) 且 \(y\Rightarrow z\)，那么有 \(x\Rightarrow y\) 或 \(y\Rightarrow x\)。
再过一个月就是 C 国成立的千年纪念日，所以 C 国的人民正在筹备盛大的游行庆典。目前 C 国得知接下来会有 \(q\) 次游行计划，第 \(i\) 次游行希望从城市 \(s_i\) 出发，经过若干个城市后，在城市 \(t_i\) 结束，且在游行过程中，一个城市可以被经过多次。为了增加游行的乐趣，每次游行还会临时修建出 \(k\)（\(0 \le k \le 2\)）条有向道路专门供本次游行使用，即其它游行计划不能通过本次游行修建的道路。
现在 C 国想知道，每次游行计划可能会经过多少座城市。
注意：临时修建出的道路可以不满足 C 国道路原有的特点。
先缩点，反正不影响可达性。
在那个性质中,\(x\Rightarrow z\) 且 \(y\Rightarrow z\)，那么 \(x\) 和 \(y\) 中有一个可达另一个，设 \(x\Rightarrow y\)，那么此时如果 \(x\) 到 \(z\) 有边，我们可以删去 \(x\) 到 \(z\) 的边。
换言说，对于一个点的所有入边，我们只保留拓扑序最大的那条边(拓扑序应该是固定的），不影响可达性。所以现在变成了一棵树的问题。要在树上增加几条边后，判断有几个点既能被 \(s\) 到达又能到达 \(t\)。
当 \(k=0\) 和 \(k=1\) 时写个分讨就行了，但是 \(k=2\) 不该有人想写分讨吧。此时可以把 \(s\)，\(t\) 和其他边的端点放在一起建出虚树，然后此时只有 \(O(k)\) 条边，用 bfs 求出可达性之后就好做了。
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int n,m,q,k,tme,dfn[N],low[N],id[N],st[N],tp,idx,hd[N],e_num,u[N],v[N],rt,fa[N][23],dep[N],dp[N],s,t,ans,l=1,r,vs[2][N],sz[N],p[N];
struct edge{
int v,nxt,f,w;
}e[N];
void add_edge(int u,int v,int f=0,int w=0)
{
e[++e_num]=(edge){v,hd[u],f,w};
hd[u]=e_num;
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void topo()
{
idx=0;
for(int i=1;i<=tme;i++)
if(!dfn[i])
st[++r]=i;
rt=st[1];
while(l<=r)
{
for(int i=hd[st[l]];i;i=e[i].nxt)
{
--dfn[e[i].v];
if(!dfn[e[i].v])
fa[e[i].v][0]=st[l],st[++r]=e[i].v;
}
++l;
}
}
void tarjan(int x)
{
dfn[x]=low[x]=++idx,st[++tp]=x;
for(int i=hd[x];i;i=e[i].nxt)
{
if(!dfn[e[i].v])
tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
else if(!id[e[i].v])
low[x]=min(low[x],dfn[e[i].v]);
}
if(dfn[x]==low[x])
{
++tme;
while(st[tp]^x)
sz[id[st[tp--]]=tme]++;
sz[id[st[tp--]]=tme]++;
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;~i;--i)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y)
return x;
for(int i=20;~i;--i)
if(fa[x][i]^fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs(int x)
{
dep[x]=dep[fa[x][0]]+1;
dp[x]=dp[fa[x][0]]+sz[x];
dfn[x]=++idx;
for(int i=1;i<=20;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=hd[x];i;i=e[i].nxt)
dfs(e[i].v);
}
int cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
void clr(int x)
{
hd[x]=vs[0][x]=vs[1][x]=0;
}
void sou(int x)
{
if(vs[0][x]&&vs[1][x])
ans+=sz[x];
for(int i=hd[x];i;i=e[i].nxt)
{
if(!e[i].f&&!e[i].w)
{
sou(e[i].v);
if(vs[0][x]&&vs[1][e[i].v])
ans+=dp[fa[e[i].v][0]]-dp[x];
}
}
}
void bfs(int x,int op)
{
low[l=r=1]=x;
vs[op][x]=1;
while(l<=r)
{
for(int i=hd[low[l]];i;i=e[i].nxt)
{
if(!vs[op][e[i].v]&&e[i].w==op)
{
vs[op][e[i].v]=1;
low[++r]=e[i].v;
}
}
++l;
}
}
void addedge(int u,int v,int f=0)
{
//printf("hjhyyds:%d %d\n",u,v);
//printf("qzm:%d %d\n",u,v);
add_edge(u,v,f,0);
add_edge(v,u,f,1);
}
int main()
{
n=read(),m=read(),q=read(),k=read();
for(int i=1;i<=m;i++)
u[i]=read(),v[i]=read(),add_edge(u[i],v[i]);
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
memset(hd,e_num=0,sizeof(hd));
memset(dfn,0,sizeof(dfn));
for(int i=1;i<=m;i++)
if(id[u[i]]^id[v[i]])
add_edge(id[u[i]],id[v[i]]),++dfn[id[v[i]]];
topo();
memset(hd,e_num=idx=0,sizeof(hd));
for(int i=1;i<=tme;i++)
if(i^rt)
add_edge(fa[i][0],i);
dfs(rt);
while(q--)
{
int rt;
scanf("%d%d",&s,&t),m=e_num=ans=0;
p[++m]=id[s],p[++m]=id[t];
//printf("%d %d\n",id[s],id[t]);
for(int i=1;i<=k;i++)
{
scanf("%d%d",u+i,v+i);
p[++m]=id[u[i]],p[++m]=id[v[i]];
//printf("%d %d\n",id[u[i]],id[v[i]]);
}
sort(p+1,p+m+1,cmp);
m=unique(p+1,p+m+1)-p-1;
for(int i=1;i<=m;i++)
clr(p[i]);
clr(rt=st[tp=1]=lca(p[1],p[m]));
for(int i=2;i<=m;i++)
clr(lca(p[i-1],p[i]));
for(int i=1;i<=m;i++)
{
if(p[i]==st[1])
continue;
int d=lca(p[i],st[tp]);
if(d^st[tp])
{
while(dfn[d]<dfn[st[tp-1]])
addedge(st[tp-1],st[tp]),--tp;
if(d^st[tp-1])
addedge(d,st[tp]),st[tp]=d;
else
addedge(d,st[tp--]);
}
st[++tp]=p[i];
}
for(int i=1;i<tp;i++)
addedge(st[i],st[i+1]);
for(int i=1;i<=k;i++)
if(id[u[i]]^id[v[i]])
addedge(id[u[i]],id[v[i]],1);
bfs(id[s],0);
bfs(id[t],1);
sou(rt);
printf("%d\n",ans);
}
}