好水的省选题，可惜我不会支配树。。

分析

从总总迹象表明，按支配关系连边，这玩意儿可以搞成一棵树

然后就引出了支配树算法（好简单）

做过ZJOI2012灭绝的应该知道灭绝树的东西，支配树其实和灭绝树一样

但由于可能有环，所以可以\(O(n^2)\)枚举删掉哪个点1无法经过哪些点求出支配点集

考虑每次加入一条边，显然一个点被修改支配关系，则它的子树都被修改，所以只需要考虑每个点的父亲是否可以滚的情况

考虑如何绕开父亲:1->x->y->u

• fa不能在1->x上，所以在1->x上打标记
• fa不能在y->u上，所以建反向边求出所有u不经过fa能到达的点

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

const int N=3005;
bool vis[N];
int n,m,q,sz[N],pa[N],id[N],Ans,d[N];
vector<int>V[N],V1[N],V2[N],ans[N],bz[N];
bool cmp(int i,int j) {
	return sz[i]>sz[j];
}
void cut(int u) {
	if(vis[u]) return;
	vis[u]=1;
	for(int v:V[u]) {
		cut(v);
	}
}
void dfs(int rt,int u) {
	if(vis[u]) return;
	vis[u]=1; ans[u].pb(rt);
	for(int v:V1[u]) {
		dfs(rt,v);
	}
}
void del(int u) {
	if(vis[u]) return;
	Ans++,vis[u]=1;
	for(int v:V2[u]) {
		del(v);
	}
}
int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++) {
		int u,v; scanf("%d%d",&u,&v);
		V[u].pb(v);
		V1[v].pb(u);
	}
	for(int i=1;i<=n;i++) {
		memset(vis,0,sizeof(vis));
		vis[i]=1,cut(1);
		for(int j=1;j<=n;j++) {
			if(!vis[j]) sz[i]++,bz[j].pb(i);
		}
	}
	for(int i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+n+1,cmp);
	for(int i=1;i<=n;i++) {
		int u=id[i]; 
		for(int fa:bz[u]) {
			if(d[fa]>d[pa[u]]) {
				pa[u]=fa;
			}
		}
		d[u]=d[pa[u]]+1;
		V2[pa[u]].pb(u);
	}
	for(int i=1;i<=n;i++) {
		memset(vis,0,sizeof(vis));
		vis[pa[i]]=1;
		dfs(i,i);
	}	
	while(q--) {
		int x,y; scanf("%d%d",&x,&y);
		memset(vis,0,sizeof(vis));
		for(;x;x=pa[x]) vis[x]=1; Ans=0;
		for(int v:ans[y]) {
			if(!vis[v]&&!vis[pa[v]]) {
				del(v);
			}
		}
		printf("%d\n",Ans);
	}
	return 0;
}

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

原文：https://www.cnblogs.com/wsfwsf/p/14861010.html