看到题目名称，我反手就是一个支配树，很快啊……哦我不会支配树啊，那没事了。
看一眼数据范围……\(n\) 只有 \(3\times10^3\)？那直接 \(O(n^2)\) 枚举删掉每个点大力求出支配集合就好了。
然后根据支配集合的大小关系建出支配树来。
考虑新加入一条边 \((x,y)\)，会有哪些点 \(i\) 在支配树上的父亲发生变化，手玩可以发现充要条件是：
-
\(x\) 不是 \(fa_i\)；
-
\(fa_i\) 不是 \(1\)；
-
从 \(1\) 走到 \(x\) 不必须经过 \(fa_i\)，即 \(fa_i\) 不支配 \(x\)；
-
从 \(y\) 走到 \(i\) 不必须经过 \(fa_i\)。
前三个条件在求支配树的时候都已经求出来了，最后一个条件建出反图，然后从每个 \(i\) 出发，钦定不能走 \(fa_i\)，看看哪些点能到就好了，也能在 \(O(n^2)\) 的时间内与处理出来。
这样我们得出了哪些点的 \(fa_i\) 发生了改变，又因为树上的支配关系改变是具有传递性的，然后再线性推一遍标记就好了，时间复杂度 \(O(n(n+q))\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct edge
{
int nxt,to;
}e[6001<<1];
int n,m,q,tot,h[3001],fa[3001],id[3001],ans;
bool vis[3001][3001][2],tag[3001];
vector<int> domain[3001];
inline int read()
{
int x=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)
c=getchar();
while(c>=‘0‘&&c<=‘9‘)
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
void print(int x)
{
if(x>=10)
print(x/10);
putchar(x%10+‘0‘);
}
inline bool cmp(int x,int y)
{
return domain[x].size()<domain[y].size();
}
inline void add(int x,int y)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
}
void dfs1(int k,int ban)
{
if(k==ban)
return;
vis[k][ban][0]=1;
for(register int i=h[k];i;i=e[i].nxt)
if(i&1)
if(!vis[e[i].to][ban][0])
dfs1(e[i].to,ban);
}
void dfs2(int k,int s,int ban)
{
if(k==ban)
return;
vis[k][s][1]=1;
for(register int i=h[k];i;i=e[i].nxt)
if(!(i&1))
if(!vis[e[i].to][s][1])
dfs2(e[i].to,s,ban);
}
int main()
{
n=read(),m=read(),q=read();
for(register int i=1;i<=m;++i)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs1(1,0);
for(register int i=1;i<=n;++i)
{
dfs1(1,i);
for(register int j=1;j<=n;++j)
if(vis[j][0][0]&&!vis[j][i][0])
domain[j].push_back(i);
}
/*for(register int i=1;i<=n;++i,puts(""))
for(register int j=0;j<(int)domain[i].size();++j)
printf("%d ",domain[i][j]);*/
for(register int i=1;i<=n;++i)
id[i]=i;
sort(id+1,id+n+1,cmp);
for(register int i=2;i<=n;++i)
for(register int j=0;j<(int)domain[i].size();++j)
if(domain[domain[i][j]].size()==domain[i].size()-1)
{
fa[i]=domain[i][j];
break;
}
for(register int i=2;i<=n;++i)
dfs2(i,i,fa[i]);
while(q--)
{
ans=0;
int x=read(),y=read();
for(register int i=1;i<=n;++i)
if(fa[i]!=1&&x!=fa[i]&&vis[x][fa[i]][0]&&vis[y][i][1])
tag[i]=1;
else
tag[i]=0;
for(register int i=1;i<=n;++i)
ans+=(tag[id[i]]|=tag[fa[id[i]]]);
print(ans);
putchar(‘\n‘);
}
return 0;
}