[省选联考 2021 A 卷] 支配

给出个有向图。定义受支配集\(D_v\)表示从\(1\)出发到\(v\)必须经过的点。

有一些询问，每次询问加入一条边之后\(D_v\)变化的个数。

保证\(1\)可以到达所有点。

\(n\le 3000,m\le 2n,q\le 2*10^4\)

其实直接套支配树板子就可以得到\(O((n+m)q\lg n)\)的做法。

分析支配树的性质：一条在原图的边\((u,v)\)，在支配树上：1. 如果为前向边或横插边，一定有\(fa_v=LCA(u,v)\)；3. 为后向边。

考虑现在加入一条边\((x,y)\)，新增的路径要经过\((x,y)\)。如果这是后向边则没有影响，如果是横插边或前向边：记\(lca=LCA(x,y)\)，\(rt\to lca\)为必经点。分析：

1. 如果有路径经过\((x,y)\)，然后经过\((w,z)\)，\(w\)在\(lca\)的子树内，\(z\)不在\(lca\)的子树内；由以上的分析可得，\(fa_z=LCA(w,z)\)。显然\(LCA(w,z)\)为\(lca\)的祖先。于是到达\(z\)之前仍然必经\(rt\to fa_z\)，没有影响。
2. 所以能影响到的点在\(lca\)子树内。并且如果能到达点\(z\)，\(fa_z=lca\)，因为还是经过了\(rt\to fa_z\)，所以也没有变化。因此能影响到的点\(z\)在\(lca\)子树内，满足\(dep_z>dep_{lca}+1\)。

进一步可以得到算法：从\(y\)出发遍历原图的边，要求不能经过\(dep_z>dep_{lca}+1\)的点，遍历到的点数就是答案。

支配树可以\(O(nm)\)预处理，一次询问遍历时间是\(O(n+m)\)。

其实后面这个问题也和Day1T3有些相像，用类似的方法做，感觉上能搞到\(O(nm)\)预处理，\(O(1)\)询问的样子。

using namespace std;
#include <bits/stdc++.h>
#define N 3005
#define M 6005
int n,m,Q;
struct EDGE{
	int to;
	EDGE *las;
};
struct Graph{
	EDGE e[M];
	int ne;
	EDGE *last[N];
	void link(int u,int v){
		e[ne]={v,last[u]};
		last[u]=e+ne++;
	}
} G,T;
int vis[N],BZ;
int anc[N][N],sz[N],fa[N],hs[N],dep[N],top[N];
bool cmpp(int x,int y){return sz[x]<sz[y];}
void BFS(int ban){
	static queue<int> q;
	vis[1]=++BZ;
	q.push(1);
	while (!q.empty()){
		int x=q.front();
		q.pop();
		for (EDGE *ei=G.last[x];ei;ei=ei->las)
			if (ei->to!=ban && vis[ei->to]!=BZ){
				vis[ei->to]=BZ;
				q.push(ei->to);
			}
	}
	for (int i=1;i<=n;++i)
		anc[i][ban]=(vis[i]!=BZ);
}
void buildT(){
	static int p[N];
	for (int i=1;i<=n;++i)
		anc[i][1]=1;
	for (int i=2;i<=n;++i)
		BFS(i);
	for (int j=1;j<=n;++j)
		for (int i=1;i<=n;++i)
			sz[j]+=anc[i][j];
	for (int i=1;i<=n;++i)
		p[i]=i;
	sort(p+1,p+n+1,cmpp);
	for (int i=1;i<=n;++i)
		for (int j=1;j<i;++j)
			if (anc[p[j]][p[i]] && !fa[p[j]])
				fa[p[j]]=p[i];
	for (int i=2;i<=n;++i)
		T.link(fa[i],i);
	for (int x=1;x<=n;++x)
		for (EDGE *ei=T.last[x];ei;ei=ei->las)
			if (sz[ei->to]>sz[hs[x]])
				hs[x]=ei->to;
	top[1]=1,dep[1]=0;
	for (int i=n;i>=1;--i){
		int x=p[i];
		for (EDGE *ei=T.last[x];ei;ei=ei->las){
			dep[ei->to]=dep[x]+1;
			top[ei->to]=(hs[x]==ei->to?top[x]:ei->to);
		}
	}
}
int LCA(int u,int v){
	while (top[u]!=top[v])
		if (dep[top[u]]>dep[top[v]])
			u=fa[top[u]];
		else
			v=fa[top[v]];
	return dep[u]<dep[v]?u:v;
}
int query(int x,int y){
	int lca=LCA(x,y);
	if (x==y || lca==fa[y] || lca==y)
		return 0;
	static queue<int> q;
	int ans=1;
	vis[y]=++BZ;
	q.push(y);
	while (!q.empty()){
		int u=q.front();
		q.pop();
		for (EDGE *ei=G.last[u];ei;ei=ei->las)
			if (dep[ei->to]>dep[lca]+1 && vis[ei->to]!=BZ){
				vis[ei->to]=BZ;
				ans++;
				q.push(ei->to);
			}
	}
	return ans;
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%d%d%d",&n,&m,&Q);
	for (int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		G.link(u,v);
	}
	buildT();
	while (Q--){
		int x,y;
		scanf("%d%d",&x,&y);
		int ans=query(x,y);
		printf("%d\n",ans);
	}
	return 0;
}

[省选联考 2021 A 卷] 支配

原文：https://www.cnblogs.com/jz-597/p/14661114.html