支配树

大家好，欢迎来到IT知识分享网。

​ 首先先要说明一下支配的概念，现在有一个有向图和起点 \(s\) ，对于点 \(u,v\) ，如果任意一条从 \(s\rightarrow u\) 的路径都要经过 \(v\) ，换种说法就是如果删去 \(u\) 就无法从 \(s\) 到 \(u\) ，那么 \(v\) 就是 \(u\) 的支配点。所有支配 \(u\) 的点的集合就是点 \(u\) 的支配集

一个支配的性质：

• 如果 \(x\) 支配 \(z\) ， \(y\) 支配 \(z\) ，那么 \(x\) 和 \(y\) 一定有支配关系。

  不然则必定有一种情况，使得删除其中一个点后，\(s\) 可从另一个点到达 \(z\)。

​ 发现这样具有树的结构，那么我们就设 \(x\) 支配集中“直接” 支配 \(x\) 的点作为 \(x\) 的父亲（你也可以简单理解为支配集最大的点）。这样形成的一棵树就是支配树。

​ 下面介绍怎么求支配树。

一、DAG（P2597 [ZJOI2012]灾难）

​ 对于一个点 \(x\) 考虑 \(x\) 的所有前驱节点\(y_i\)。要支配节点 \(x\) ，那么就要支配所有的 \(y_i\) ，那么 \(x\) 的支配点就是所有 \(y_i\) 支配点的公共部分，对应到支配树上就是所有 \(y_i\) 的lca。

​ 所以我们按拓扑序来遍历DAG，这样保证在求 \(x\) 时所有 \(x\) 的前驱都求出来了。

​ 因为我们要动态插入点，所以只能用倍增+dep的方法求lca。

while(p.size()){
	int x=p.front();p.pop();
	int lc=b[x][0];
	for(int i=1;i<b[x].size();++i)lc=lca(lc,b[x][i]);
	f[x][0]=lc,de[x]=de[lc]+1;
	for(int i=1;i<=lo[n];++i)f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];i;i=a[i].ne){
		int y=a[i].y;
		if(!--rd[y])p.push(y);
	}
}

二、一般有向图（P5180 【模板】支配树）

​ \(O(n^2)\)的方法是暴力删点，然后遍历一次图找无法到达的点。

​ 考虑优化。

​ 先从图中抠出一个dfs生成树，保证 \(x\) 的支配点一定是 \(x\) 在dfs生成树上的祖先节点（或许自证不难？）

​ 然后引入一个概念——半支配点\(semi_x\)：dfs序最小的点且满足，可以通过一条路径\(p_1,p_2,…,p_k\)到达 \(x\) ，且 \(\forall \;i\in[2,k-1],dfs_{p_i}>dfs_x\) 。

​ 我们先不管这个dfs序最小的限制，假如就存在一个这样的点 \(u\) 满足半支配点的要求，那么也就表示 \(\text{lca}_{u,x}\rightarrow x\) 这一条路径上的点都不会是 \(x\) 的支配点，因为 \(dfs >dfs_x\)的点一定不是\(\text{lca}_{u,x}\rightarrow x\) 这一条路径上的点。

​ 但由于dfs生成树一定没有 \(x\rightarrow y\) 且 \(dfs_x<dfs_y\) 而且 \(x\) 不是 \(y\) 父亲的边，所以可以确定，在dfs序最小的情况下 \(u\) 一定是 \(x\) 的祖先。同时这个dfs序最小就保证了 \(u\) 深度最小，这样排除一定不是答案的点也就越多。

​ 这样就有一个很神奇的做法：对于每一个 \(x\) ，在dfs树上从 \(semi_x\) 向 \(x\) 连边，删掉其他边，支配关系不变，这样就可以转化成DAG。

​ 为什么？就是对于 \(x\) 来说，其他所有的边真正的作用就是排除了 \(semi_x\rightarrow x\) 这条路径上的点作为 \(x\) 和 \(x\) 子树的支配点，那么就可以将其化简为\(semi_x\rightarrow x\)这条边。

​ 之后考虑求半支配点 \(semi_x\) 。

​ 我们先从dfs序降序遍历点。这样对于 \(x\) 的前驱 \(y\) ，若\(dfs_y<dfs_x\)，即 \(y\) 是 \(x\) 的祖先，直接用 \(dfs_y\) 更新答案，否则就从 \(y\) 向上跳，保持\(dfs_y>dfs_x\)，对于这些 \(y\) 用 \(semi_y\) 更新答案。

​ 显然不能暴力跳父亲，发现满足的点 \(y\) 是已经遍历过的点，而且维护的结构是树，就可以用并查集动态维护已经遍历完的树的部分。代码：

int find(int x){//并查集部分
	if(x^f[x]){
		int fx=f[x];
		f[x]=find(f[x]);
		val[x]=min(val[x],val[fx]);//维护x到当前顶部的最小值
	}
	return f[x];
}

for(int i=1;i<=n;++i)f[i]=i,val[i]=dfs[i];
for(int i=n;i>=2;--i){
	int x=id[i];
	for(int j=0;j<pr[x].size();++j){
		int y=pr[x][j];
		find(y);//将y是x祖先的情况合并了，因为val[y]初始值就是dfs[y]
		val[x]=min(val[x],val[y]);
	}
	f[x]=fa[x];
	zps::add(id[val[x]],x);//id[x]记录dfs为x的节点编号
}

​ 注意此时内部DAG求支配树的边数为2n！！

三、一个小运用（P7520 [省选联考 2021 A 卷] 支配）

给定一个有向图，q 次互相独立的询问，每次询问给出一条有向边，求加入该条边后，有多少个顶点的受支配集发生了变化。\(n \le 3 \times 10^3, m \le 2 \times n, q \le2\times 10^4\)

​ 首先先建立支配树，naive的想，加入 \(x\rightarrow y\) 这条边之后，只需要考虑 \(y\) 这个点的支配集是否会改变，若改变则答案是\(si_y\)。

​ 考虑如何判断，因为是加边，那么受支配集只会减少。那么我们可以通过判断 \(fa_y\) 是否还是 \(y\) 的支配点来判断 \(y\) 受支配集是否改变，预处理出 \(f_{x,y}\) 表示在删去 \(fa_x\) 之后 \(1\) 号点能否到达 \(y\) ，\(g_{x,y}\) 表示在删去\(fa_x\)之后，\(y\) 能否到达 \(x\) 。

​ 但是会改变的可能不止是 \(y\) ，那么我们就扫一遍\(1\sim n\)，若 \(x\) 的受支配集会改变，那么 \(x\) 的子树内所有的点的受支配集一定会改变，直接统计答案即可。

四、一个小总结

​ 感觉当前支配树的运用、发掘还很少，题目当然少的可怜，除了成树之后的树上操作（会有吗…）感觉支配树最难的还是关于支配树的变化问题（就是上面的运用），感觉要多考虑一下最早提出来的性质：如果 \(x\) 支配 \(z\) ， \(y\) 支配 \(z\) ，那么 \(x\) 和 \(y\) 一定有支配关系。