2021省选联考A卷解题报告

考试总结

---

退役了。游记

难度可能是绿紫紫紫蓝紫，而且有三四道题目卡常，还有一道题目超纲（CCF啪啪打脸）。

更好的阅读体验

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

题意：$n$张卡牌，正面数字为$a_i$，反面数字为$b_i$，一开始所有卡牌正面朝上，可以翻动至多$m$张卡牌，使得朝上的数字极差最小。

分析：

特别简单的签到题，然后CCF就成功脚造数据。（不输入$m$的错误贪心还能过就很离谱）

考虑极差最小等价于值在数轴上对应的区间长度最小，把$a$与$b$的值放在一起排序，在上面双指针求解就好了。

时间复杂度：$O(n\log n)$。

#include<stdio.h>
#include<algorithm>
#define inf 1000000001
using namespace std;
const int maxn=1000005;
int n,m,ans;
int a[maxn],b[maxn],vis[maxn];
pair<int,int>c[maxn<<1];
inline int get(int x){
    return x>n? x-n:x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),c[i].first=a[i],c[i].second=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),c[n+i].first=b[i],c[n+i].second=n+i;
    sort(c+1,c+1+2*n);
    int l=1,r=0,cnta=0,cnt=0;
    while(cnt<n||cnta<n-m){
        r++;
        if(c[r].second<=n)
            cnta++;
        if(vis[get(c[r].second)]==0)
            cnt++;
        vis[get(c[r].second)]++;
    }
    ans=c[r].first-c[l].first;
    while(l<2*n&&r<=2*n){
        if(c[l].second<=n)
            cnta--;
        vis[get(c[l].second)]--;
        if(vis[get(c[l].second)]==0)
            cnt--;
        l++;
        while(cnt<n||(r<=2*n&&cnta<n-m)){
            r++;
            if(c[r].second<=n)
                cnta++;
            if(vis[get(c[r].second)]==0)
                cnt++;
            vis[get(c[r].second)]++;
        }
        if(r>2*n)
            break;
        ans=min(ans,c[r].first-c[l].first);
    }
    printf("%d\n",ans);
    return 0;
}

P7515 [省选联考 2021 A 卷] 矩阵游戏

可见P7515 [省选联考 2021 A 卷] 矩阵游戏解题报告

题意：

给定大小为$(n-1)\times(m-1)$的矩阵$b$，求生成任意一个满足条件的$a$满足：

• $a$的大小为$n\times m$；
• $b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$；
• $0\leqslant a_{i,j}\leqslant 10^6$

保证$0\leqslant b_{i,j}\leqslant 4\times 10^6$，$2\leqslant n,m\leqslant 300$。

分析：

可能是暗中送我退役的一道题，我要是把这个思路想下去做掉这道题，那我剩下的题用头打都能进队啊！！！！！！！！！！！！！！！！！！！！！！！！！！！！

技不如人，肝败吓疯。

首先不考虑$0\leqslant a_{i,j}\leqslant 10^6$，并钦定$a_{i,1}=a_{1,j}=0$，不难发现可以生成一组解$a'$。

我们考虑通过调整某些位置的权值使得最后的解权值满足限制。

发现对某一行交替$+r,-r,+r,-r\cdots$后的解仍然满足矩阵$b$的限制；同理，对某一列交替$+c,-c,+c,-c\cdots$后的解也仍然满足矩阵$b$的限制。

不难发现任意一组解都可以被这样表示出来：

$$\begin{bmatrix}a'_{1,1}+r_1+c_1&a'_{1,2}-r_1+c_2&a'_{1,3}+r_1+c_3&\cdots\\a'_{2,1}+r_2-c_1& a'_{2,2}-r_2-c_2& a'_{2,3}+r_2-c_3&\cdots\\a'_{3,1}+r_3+c_1& a'_{3,2}-r_3+c_2&a'_{3,3}+r_3+c_3&\cdots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix}$$

再考虑$0\leqslant a_{i,j}\leqslant 10^6$这一限制，不难发现把$c$序列与$r$序列看做未知量之后可以对其进行差分约束。

但是对于同号的不等式是很难进行差分约束的，考虑定义$c'_{k}=\begin{cases}-c_k&k\equiv 1\pmod 2\\c_k&k\equiv 0\pmod 2\end{cases}$,$r'_{k}=\begin{cases}r_k&k\equiv 1\pmod 2\\-r_k&k\equiv 0\pmod 2\end{cases}$

然后再次带入上面的解可以得到一个很优美的形式：

$$\begin{bmatrix}a'_{1,1}+r'_1-c'_1&a'_{1,2}-r'_1+c'_2&a'_{1,3}+r'_1-c'_3&\cdots\\a'_{2,1}-r'_2+c'_1& a'_{2,2}+r'_2-c'_2& a'_{2,3}-r'_2+c'_3&\cdots\\a'_{3,1}+r'_3-c'_1& a'_{3,2}-r'_3+c'_2&a'_{3,3}+r'_3-c'_3&\cdots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix}$$

这样就可以进行差分约束了，复杂度：$O((n+m)nm)$。

Bellman Ford被卡常了（需要特判才能过），迫不得已用了spfa/kk

#include<stdio.h>
#include<queue>
#include<vector>
#define inf 10000000000000000
using namespace std;
const int maxn=305,maxm=maxn*maxn*2;
int T,n,m,e;
int a[maxn][maxn],b[maxn][maxn],vis[maxn<<1],tot[maxn<<1];
vector<int>v[maxn<<1],w[maxn<<1];
long long dis[maxn<<1];
queue<int>q;
inline void add(int x,int y,int z){
    v[x].push_back(y),w[x].push_back(z);
}
inline void limit(int x,int y,int v){
    add(x,y,v);//v+x-y>=0
    add(y,x,1000000-v);//v+x-y<=1000000
}
int spfa(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n+m;i++)
        dis[i]=inf,tot[i]=0,vis[i]=0;
    dis[1]=0,vis[1]=1,q.push(1);
    while(!q.empty()){
        int x=q.front();
        tot[x]++;
        if(tot[x]>n+m)
            return 1;
        q.pop();
        for(int i=0;i<v[x].size();i++){
            int y=v[x][i],z=w[x][i];
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                if(vis[y]==0)
                    vis[y]=1,q.push(y);
            }
        }
        vis[x]=0;
    }
    return 0;
}
inline int calc(int x,int y){
    return a[x][y]+(int)(((x+y)&1)? (dis[n+y]-dis[x]):(dis[x]-dis[n+y]));
}
int main(){
    scanf("%d",&T);
    while(T--){
        e=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                scanf("%d",&b[i][j]);
        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
                a[i][j]=b[i-1][j-1]-a[i-1][j-1]-a[i-1][j]-a[i][j-1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if((i+j)&1)
                    limit(n+j,i,a[i][j]);
                else limit(i,n+j,a[i][j]);
            }
        if(spfa()){
            puts("NO");
            for(int i=1;i<=n+m;i++)
                v[i].clear(),w[i].clear();
            continue;
        }
        puts("YES");
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",calc(i,j),j==m? '\n':' '),a[i][j]=0;
        for(int i=1;i<=n+m;i++)
            v[i].clear(),w[i].clear();
    }
    return 0;
}

P7516 [省选联考 2021 A/B 卷] 图函数

可见P7516 [省选联考 2021 A/B 卷] 图函数解题报告

题意：

给定一张$n$个点$m$条边的有向图$G$，定义函数$f(u,G)$的值为下列操作的返回值：

设$cnt=0,G'=G$，然后按$1$到$n$的顺序枚举点$v$，如果$G'$中$v$与$u$能双向到达，那么$cnt++$，并删去结点$v$，最后返回$cnt$。

定义$h(G)=\sum_{i=1}^n f(i,G)$，并定义$G_i$为图$G$删除边$1\cdots i$后的图，求出$h(G_{0\cdots n})$。

$1\leqslant n\leqslant 10^3,1\leqslant m\leqslant 2\times 10^5$。

分析：

定义$g_{x,y}(x\leqslant y)$为$x$经过$[x,n]$的点能否到达$y$，同样设$g_{x,y}(x>y)$为$x$经过$[y,n]$的点能否到达$y$，那么对于图$G$，求的其实就是$\sum_{i\ne j}g_{i,j}\text{&}g_{j,i}$。

发现如果图改变需要重新处理值，这肯定会超时，因此将$g_{x,y}$中是否能到达改为删除最多的边使得能让其到达的边数（无法到达则为$0$）。

那么如果我们处理出$g_{x,y}$，我们可以求出答案的差分数组，然后前缀和就好了。

考虑类似Floyd的做法，从大到小枚举中转点$k$（这样做可以让循环到$k$时经过的点全部大于等于$k$，便于统计答案），然后对路径进行合并。

具体地，我们对于$\leqslant k$且可以经过$>k$的结点到达$k$（其实就是判断当时的$g_{i,k}$是否非零）的点$i$，枚举终点$j$，那么会存在一条$i\rightarrow k\rightarrow j$的路径，且不难发现这条路径删除的边数为$\min\{g_{i,k},g_{k,j}\}$，用这个权值更新$g_{i,j}$就好了。

同理对于$>k$且可以经过$>k$的结点到达$k$的点$i$，枚举终点$j$（这里的$j$要小于$k$，否则答案会算重。但其实算重也没关系，因为这一部分的答案已经在之前更新过了），按上面同样的方式更新答案就好了。

时间复杂度：$O(n^3+m)$。

#include<stdio.h>
const int maxn=1005,maxm=200005;
int n,m;
int g[maxn][maxn],sum[maxm],ans[maxm];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        g[i][i]=m+1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]=i;
    }
    for(int k=n;k>=1;k--){
        for(int i=k;i<=n;i++)
            sum[min(g[i][k],g[k][i])]++;
        for(int i=1;i<=k;i++)
            if(g[i][k])
                for(int j=1;j<=n;j++)
                    g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));
        for(int i=k+1;i<=n;i++)
            if(g[i][k])
                for(int j=1;j<k;j++)
                    g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));
    }
    for(int i=m;i>=1;i--)
        sum[i]+=sum[i+1];
    for(int i=1;i<=m+1;i++)
        printf("%d%c",sum[i],i==m+1? '\n':' ');
    return 0;
}

P7518 [省选联考 2021 A/B 卷] 宝石

可见P7518 [省选联考 2021 A/B 卷] 宝石解题报告

题意：

给定一颗$n$个点的带点权的树，以及一个长度为$c$的匹配序列，（点权与序列的值域为$[1,m]$），$q$次询问，每次询问$x$到$y$的有向路径与匹配序列匹配的最长前缀的长度。

$1\leqslant n,q\leqslant 2\times 10^5,1\leqslant c\leqslant m\leqslant 5\times 10^4$。

分析：

考场写了一个5k的树分块$O((n+q+m\alpha(n))\sqrt{n})$的做法，然后被卡常卡成$35pts$就很离谱。

（该部分可略过）
在树上撒$\sqrt{n}$个关键点，每个点与其祖先里的关键点距离为$\sqrt{n}$，然后发现可以把询问的路径分成$4$个散块和$2$个整块，散块暴力跳（记得把$lca$到另一端的路径反向，我因为反向调了一个多小时），整块可以预处理第$i$个关键点跳到祖先关键点这一条链，从位置$j$开始匹配能匹配到哪里，不难发现（我想了十几分钟）可以用并查集维护所有位置同时进行匹配，同样还要反过来做一遍。
具体地，可以把整块对应的链上权值序列当成一个普通的序列，与长度为m的串进行匹配，然后对于每个位置可以维护它在匹配的过程中到了哪一个位置，不难发现把相同的位置在匹配的过程中会不断合并，那么直接上并查集就好了。

然后发现$O(n\log n+q\log n\log m)$的树上倍增好想好写的一批。

首先进行一次转化，把点权转化为在序列中的位置，这样好做一些。

考虑预处理$x$向上跳第一个点权为$c$的点的位置，这是一个经典问题，在树上用主席树完成就好了，时空复杂度均为$O(n\log m)$。

然后再按照树上倍增的套路预处理一个$inc_{x,k}$表示$x$向上跳，从当前点权$w_x$匹配到$w_x+2^k$的位置，以及$dec_{x,k}$表示$x$向上跳，从当前点权$w_x$反向匹配到$w_x-2^k$的位置。我们首先用主席树帮忙处理出$inc_{x,0}$与$dec_{x,0}$，然后直接合并就好了。

对于询问$(x,y)$，设$z=lca(x,y)$，考虑让$x$跳到第一个点权为$1$的点开始匹配（需要特判一下跳出$x\rightarrow z$这一条链的情况），然后用树上倍增暴力跳$inc$数组直到跳出$x\rightarrow z$这一条链。

之后，我们发现$y$不能进行类似的操作，因为我们不知道结尾的点权为多少，不难发现答案具有可二分性，直接二分最后的位置，然后按照上面的方法跳$dec$就好了。

时间复杂度：$O(n\log n+q\log n\log m)$。

代码常数似乎很大。

#include<stdio.h>
const int maxm=50005,maxn=200005,maxe=maxn<<1,maxk=25;
int n,m,c,e,q,tot;
int p[maxm],w[maxn],start[maxn],to[maxe],then[maxe],fore[maxn][maxk],dep[maxn],pos[maxm];
int lc[maxn*maxk],rc[maxn*maxk],res[maxn*maxk],rt[maxn],inc[maxn][maxk],dec[maxn][maxk];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void build(int l,int r,int &now){
    if(now==0)
        now=++tot;
    if(l==r){
        res[now]=-1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc[now]),build(mid+1,r,rc[now]);
}
inline int newnode(int x){
    tot++,lc[tot]=lc[x],rc[tot]=rc[x],res[tot]=res[x];
    return tot;
}
void update(int l,int r,int &now,int pos,int v){
    now=newnode(now);
    if(l==r){
        res[now]=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        update(l,mid,lc[now],pos,v);
    else update(mid+1,r,rc[now],pos,v);
}
int query(int l,int r,int now,int pos){
    if(l==r)
        return res[now];
    int mid=(l+r)>>1;
    if(pos<=mid)
        return query(l,mid,lc[now],pos);
    return query(mid+1,r,rc[now],pos);
}
void dfs(int x,int last){
    dep[x]=dep[last]+1,fore[x][0]=last,rt[x]=rt[last];
    if(w[x]!=-1)
        update(1,c,rt[x],w[x],x);
    inc[x][0]=(w[x]==-1||w[x]==c)? -1:query(1,c,rt[x],w[x]+1);
    dec[x][0]=(w[x]==-1||w[x]==1)? -1:query(1,c,rt[x],w[x]-1);
    for(int i=1;i<=20;i++){
        fore[x][i]=fore[fore[x][i-1]][i-1];
        inc[x][i]=inc[x][i-1]==-1? -1:inc[inc[x][i-1]][i-1];
        dec[x][i]=dec[x][i-1]==-1? -1:dec[dec[x][i-1]][i-1];
    }
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        a+=b,b=a-b,a-=b;
    for(int i=20;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=20;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
int check(int x,int z,int now,int goal){
    x=query(1,c,rt[x],goal);
    if(x==-1||dep[x]<dep[z])
        return 0;
    for(int i=20;i>=0;i--)
        if(dec[x][i]!=-1&&dep[dec[x][i]]>dep[z])
            x=dec[x][i];
    return w[x]<=now;
}
int main(){
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=m;i++)
        pos[i]=-1;
    for(int i=1;i<=c;i++)
        scanf("%d",&p[i]),pos[p[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]),w[i]=pos[w[i]];
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    build(1,c,rt[0]),dfs(1,0);
    scanf("%d",&q);
    while(q--){
        int x,y,z,res=0;
        scanf("%d%d",&x,&y),z=lca(x,y);
        x=query(1,c,rt[x],1);
        if(x!=-1&&dep[x]>=dep[z]){
            for(int i=20;i>=0;i--)
                if(inc[x][i]!=-1&&dep[inc[x][i]]>=dep[z])
                    x=inc[x][i];
            res=w[x];
        }
        int L=res,R=c+1;
        while(L+1<R){
            int mid=(L+R)>>1;
            if(check(y,z,res+1,mid))
                L=mid;
            else R=mid;
        }
        printf("%d\n",L);
    }
    return 0;
}

P7519 [省选联考 2021 A/B 卷] 滚榜

可见P7519 [省选联考 2021 A/B 卷] 滚榜解题报告

题意：给定$n$支队伍，每支队伍有权值$a_i$。给定$m$，将$m$分成若干个数之和，按不降顺序分配给$n$个队伍，已知每次分配都会让分配给的队伍权值变为最大（权值相同比较编号大小，小的优先），求分配方案数。（$1\leqslant n\leqslant 13,1\leqslant m\leqslant 500$）

很简单的状压dp+费用提前，但考场降智了，没想到。

设$f_{i,j,k}$为当前分配完的队伍集合为$i$，上一个分配的队伍为$j$，一共消耗的权值大小为$k$的方案数，可是由于分配权值的顺序必须不降，所以还得带上另一个参数来表示上一次分配的权值，可是这样就是$O(2^nn^2m^2)$的了，比阶乘还劣。

考虑表示出或消除这个参数，根据上面的定义表示出这个参数比较难，因此我们想一想如何将这个参数的费用消除掉。

我们先想一想当我们确定了分配顺序应该怎么判断：我们按照顺序给每个队伍分配最少的权值，最后如果分配失败就说明方案失败，否则可以直接把所有剩下权值分配给最后一个队伍。

我们考虑剩下的权值不分配给最后一个队伍的情况，这时可以对于一个队伍后缀增加一个不递减的权值序列，而对这个序列差分后可以知道这个权值序列可以分成若干次给某个后缀加上相同的权值。

这提醒了我们使用费用提前，$f_{0,0,0}$转移到$f_{i,j,k}$（其中$i$集合仅含$j$）时，不难发现需要给$j$队伍增加权值$a_p-a_j+[p<j]$（设一开始权值最大的队伍为$p$），而根据上面的思考可以知道这个权值在以后每个队伍都需要进行分配，那么我们直接将权值乘$n$，提前计算费用即可。

同理，对$f_{i,j,k}$转移到$f_{i',j',k'}$，我们对于当前队伍需要增加$a_j-a_{j'}+[j<j']$的权值，我们将权值乘$|i|$就可以消除后续的贡献。

时间复杂度：$O(2^nn^2m)$，用$\text{lowbit}$来枚举可以卡卡常。

#include<stdio.h>
#define lowbit(x) x&-x
const int maxn=13,maxm=505,maxk=(1<<maxn);
int n,m,k,maxx,maxp;
int a[maxn+1],tot[maxk],p[maxk];
long long ans;
long long f[maxk][maxn+1][maxm];
inline int max(int a ,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]),p[1<<(i-1)]=i;
        if(a[i]>maxx)
            maxx=a[i],maxp=i;
    }
    k=(1<<n)-1,tot[0]=0;
    for(int i=1;i<=k;i++)
        tot[i]=tot[i>>1]+(i&1);
    for(int i=1;i<=n;i++){
        int cost=n*(maxx-a[i]+(maxp<i));
        if(cost<=m)
            f[1<<(i-1)][i][cost]=1;
    }
    for(int i=1;i<k;i++)
        for(int j=i;j;j-=lowbit(j))
            for(int s=0;s<=m;s++){
                int v=lowbit(j),now=p[v];
                if(f[i][now][s]==0)
                    continue;
                for(int t=1;t<=n;t++)
                    if(((i>>(t-1))&1)==0){
                        int cost=s+(n-tot[i])*max(a[now]-a[t]+(now<t),0);
                        if(cost<=m)
                            f[i|(1<<(t-1))][t][cost]+=f[i][now][s];
                    }
            }
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=f[k][i][j];
    printf("%lld\n",ans);
    return 0;
}

P7520 [省选联考 2021 A 卷] 支配

可见P7520 [省选联考 2021 A 卷] 支配解题报告

题意：

定义一个点$x$支配另一个点$y$当且仅当结点$1$到达结点$y$的每一条路径都要经过$x$，且点$y$的受支配集$D_y$为所有支配$y$的$x$形成的集合。

给定一个$n$个点$m$条边的图$G$，进行$q$次相互独立的询问，每次询问加入边$(x,y)$后有多少个点的受支配集有变化。

$1\leqslant n\leqslant 3000,1\leqslant m\leqslant 2\times n,1\leqslant q\leqslant 2\times 10^4$。

分析：

似乎是支配树裸题，但我不会支配树/kk。

当我们不知道支配树时，应该怎么想到支配树呢？

考虑$1$到结点$x$的所有路径一定是不断“扩张”然后不断“收束”到一个点上，然后继续“扩张”与“收束”的一个过程，而每次“收束”到的点都是$x$的支配点。

不难发现除了结点$1$外任意结点$x$都有且仅有一个极大支配点$fa_x=y$，也就是说$D_x=D_y\cup\{x\}$，那么如果我们将$x$与$y$连一条边的话，根据支配的定义一定不会形成环，那么就会形成一个$n$个结点，$n-1$条边的无向无环联通图——支配树。

如何建出支配树呢？这里介绍一种$O(n^2)$的简单做法。

考虑设$delp_{x,y}$表示删除结点$x$后，结点$1$是否能到达结点$y$，那么我们只需要枚举$x$，然后每次$\text{dfs}$就可以$O(n^2)$的求出这个数组了。

又由于$delp_{x,y}=0$与$x$支配$y$等价，因此我们可以求出所有结点的受支配集。

那么我们对于每个点枚举它受支配集中每一个点，按照极大支配点的定义进行判断就好了。

建出支配树，又怎么求解呢？（设加入的边为$(u,v)$）

对于每一个点$x$，不难发现它的受支配集会改变当且仅当$fa_x$的受支配集改变或者$fa_x$不再支配$x$。（由极大支配点的定义可得）

那么我们从上到下遍历支配树（不要直接遍历，最好用$dfs$序或者$bfs$序，本文使用$bfs$序，也就是所有点按照支配集大小进行排序的结果），问题转化为判断一个点的极大支配点$fa_x$是否还支配$x$。

很容易发现支配树的支配关系是等价于原图的（这也是CCF设置图是一个树这个部分分的原因），那么我们只需要判断删除$x$的父亲从$1$是否能到达$u$，而$v$是否能到达$x$就好了。

那么我们再$O(n^2)$预处理一个$delf_{x,y}$表示删除$x$的父亲后$y$是否能到达$x$就做完这道题了。

时间复杂度：$O(n(n+q))$。

代码被卡常了，交换了$delp_{x,y}$与$delf_{x,y}$定义中的$x$与$y$才能过。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=3005;
int n,m,q,e;
int bfn[maxn],fa[maxn],t[maxn],ok[maxn];
int delp[maxn][maxn],delf[maxn][maxn];//delp[y][x]: del x 1 to y ; delf[y][x]: del fa[x] 1 to y
vector<int>g[maxn],rg[maxn],d[maxn];
inline int cmp(int x,int y){
    return d[x].size()<d[y].size();
}
void getdelp(int x,int p){
    if(x==p)
        return ;
    delp[x][p]=1;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(delp[y][p]==0)
            getdelp(y,p);
    }
}
void getdelf(int x,int p){
    if(x==fa[p])
        return ;
    delf[x][p]=1;
    for(int i=0;i<rg[x].size();i++){
        int y=rg[x][i];
        if(delf[y][p]==0)
            getdelf(y,p);
    }
}
void read(int &x){
    x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int x,y;
        read(x),read(y);
        g[x].push_back(y),rg[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        getdelp(1,i);
        for(int j=1;j<=n;j++)
            if(delp[j][i]==0)
                d[j].push_back(i);
    }
    for(int i=2;i<=n;i++)
        for(int j=0;j<d[i].size();j++)
            if(d[d[i][j]].size()==d[i].size()-1){
                fa[i]=d[i][j];
                break;
            }
    for(int i=1;i<=n;i++)
        bfn[i]=i;
    sort(bfn+1,bfn+1+n,cmp);
    for(int i=2;i<=n;i++)
        getdelf(i,i);
    for(int i=1;i<=q;i++){
        int x,y,res=0;
        read(x),read(y);
        for(int j=1;j<=n;j++)
            if(fa[j]!=1&&fa[j]!=x&&delp[x][fa[j]]&&delf[y][j])
                ok[j]=1;
        for(int j=2;j<=n;j++){
            ok[bfn[j]]|=ok[fa[bfn[j]]];
            res+=ok[bfn[j]];
        }
        for(int j=1;j<=n;j++)
            ok[j]=0;
        printf("%d\n",res);
    }
    return 0;
}