P7520 [省选联考 2021 A 卷] 支配（题解）

xuyan1 · 2025-10-23 10:32:32 · 题解

题意

给定一张 n 个点 m 条边的有向图 G，对于任意两个点 u, v，若从顶点 1 出发到达顶点 v 的所有路径都需要经过顶点 u，则称顶点 u 支配顶点 v。特别地，每个顶点支配其自身。

对于任意一个点 v，我们将图中支配顶点 v 的顶点集合称为 v 的受支配集 D_v。

现在有 q 次互相独立的询问，每次询问给出一条有向边，请你回答在图 G 中加入该条边后，有多少个顶点的受支配集发生了变化。

数据保证给出的图 G 中，从 1 号点出发能到达所有其他点，并且图中不包含重边与自环。

对于所有测试数据：1 \le n \le 3 \times {10}^3，1 \le m \le 2 \times n，1 \le q \le 2 \times {10}^4。

O(n(n+m)) 求受支配集

D_v=\sum_{u=1}^n [P(1,u,v)]

考虑朴素求 $D_v$，枚举一个 $u$，dfs查看从 $1$ 出发是否可以到 $v$，如可以，则把 $u$ 加入 $D_v$。 - 这需要先枚举 $v$，再枚举 $u$，再dfs。 - 显然可以反过来，先枚举 $u$，再dfs，此时 $u$ 可以加入所有无法到达的点的受支配集。 # 求支配树 ## 性质 - 传递关系：若 $x$ 支配 $y$，$y$ 支配 $z$，则 $x$ 支配 $z$。 - 链式关系：若 $x$ 支配 $a$，$y$ 也支配 $a$，则 $x,y$ 之间也存在支配关系。如不然则必定有一种情况，使得删除其中一个点后，$1$ 可从另一个点到达 $a$。 ## 支配树 - 每个点与直接支配点（受支配集中距离自己最近的点）连边 - $x$ 的支配集为支配树上所有 $x$ 的祖先。 ## 构建支配树 ### 方法1 $x$ 的支配集中，$fa_x$ 是支配集大小最大的那个点。 ### 方法2 类似于拓扑排序，把支配关系看作有向边，首先把 $1$ 入队，然后重复进行如下操作： - 取出队头 $u$，对于所有受支配集中存在点 $u$ 的点，把 $u$ 从受支配集中删掉。 - 对于所有没有入队并且受支配集中只剩下本身（支配集大小为 $1$ ）的点 $v$ 入队，连边 $(u,v)$。 # 求解对于加入的每条边 $(x\to y)$，点 $v$ 的受支配集改变当且仅当： - $fa[v]$ 的受支配集改变； - 或者 $fa[v]$ 不再支配 $v

从 v 向上一直追溯，一定存在一个位置是第二种情况（存在一个 fa[v'] 不再支配 v'），则这个 v'在支配树中的子树中的点都受影响。（可以dfn序上子树差分）

因此找到所有这样的 v' 即可。

这等价于考察加边 (x,y) 之后，每个点 v 的 fa 是否仍然支配它。对于点 v：

找到路径 1\to x\to y \to v，其中 1\to x,y\to v 都不经过 fa[v]；
- 如果先枚举 $v$，再在反图上去掉 $fa[v]$ 后做dfs将复杂度巨大。 - 可以事先枚举 $v$，在反图上去掉 $fa[v]$ 后做dfs，能到的点都是 $y$。即把 $v$ 存到 $y$ 的邻接表 $adj[y]$ 中。

对每组询问 x,y：

枚举 v\in adj[y]，查看 1\rightarrow x 是否可以不经过 fa[v]，如可以，在 v 的子树上打标记。

#include<bits/stdc++.h>
using namespace std;
const int N=3000+5;
vector<int> Adj[N],szpj[N],T[N],AdjT[N],Adj1[N];
int n,m,f[N];
bool vis[N],vis0[N];
void dfs(int u,int no){
    vis[u]=1;
    for(auto v:Adj[u]){
        if(vis[v]||v==no) continue;
        dfs(v,no);
    }
}

void dfs0(int u){
    vis0[u]=1;
    for(auto v:Adj[u]){
        if(vis0[v]) continue;
        dfs0(v);
    }
}
int sz[N],pre[N],t=0;
void dfsT(int u,int fa){
    sz[u]=1;
    pre[u]=++t;
    for(auto v:T[u]){
        if(v==fa) continue;
        dfsT(v,u);
        sz[u]+=sz[v];
    }
}
void dfs1(int u,int no,int U){
    if(u==no) return;
    vis[u]=1;
    Adj1[u].push_back(U);
    for(auto v:AdjT[u]){
        if(vis[v]||v==no) continue;
        dfs1(v,no,U);
    }
}
int c[N];
int main(){
    int q;
    cin>>n>>m;
    cin>>q;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        Adj[u].push_back(v);
        AdjT[v].push_back(u);
    }
    dfs0(1);
    // speical for node 1
    for(int i=1;i<=n;i++){
        szpj[i].push_back(1);
    }
    for(int i=2;i<=n;i++){
        memset(vis,0,sizeof vis);
        dfs(1,i);
        for(int j=1;j<=n;j++){
            if(vis0[j]&&vis[j]==0){
                szpj[j].push_back(i);
            }
        }
    }
    for(int i=2;i<=n;i++){
        int maxj=0;
        for(auto j:szpj[i]){
            if(j==i) continue;
            if(szpj[j].size()>szpj[maxj].size()) maxj=j;
        }
        T[maxj].push_back(i);
        f[i]=maxj;
    }
    dfsT(1,0);
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        dfs1(i,f[i],i);
    }
    for(int i=1;i<=q;i++){
        cin>>u>>v;
        memset(c,0,sizeof c);
        int ans=0;
        for(auto j:Adj1[v]){
            if(f[j]==0) continue;
            if(!(pre[u]>=pre[f[j]]&&pre[u]<pre[f[j]]+sz[f[j]])){
                c[pre[j]]++;
                c[pre[j]+sz[j]]--;
            }
        }
        for(int j=1;j<=n;j++) c[j]+=c[j-1];
        for(int j=1;j<=n;j++) ans+=!!c[j];
        cout<<ans<<"\n";
    }

    return 0;
}