这篇文章是作者准备发表在洛谷题解区里的，然后上 wikioi 发现没有这道题。

支配树

作者写这篇文章的原因主要是现有题解要么就毫无证明，要么证明过程不太直观、概念不太清晰，在我的学习过程中困扰了我很久。

我是农历年前学的，由于实力比较弱，那时候经常坐在房间椅子上一个下午想这个算法，勉强看懂证明后草草放弃。这几天回想到这个算法，仔细思考想清楚了之后决定写下本文，方便给像我这样的学习者一个向导。

言归正传，由于作者我之前主要是根据这篇巨佬的文章学习的，因此在表示和论述方法上会有相似，但是证明过程和内容编排多数为自己的想法，使用了更感性的证明论述方法。如果您学术目的比较强，也可以去参考那篇文章。

注例

这里给出了一些本文符号代表的含义，读者不理解时可以来这里检索

在本文中，使用代指，关于的比较即为的比较。
文章中用表示到在 dfs 树上的路径，用表示在图上的路径。
本文中的以及默认指支配树上的 / ，如果指 dfs 树上的会写作。

定义

作者自己学习过程中的一大难点就是没有抓住准确的定义，经过摸索猜测联系下文等才理解。

这一部分会对支配，支配树，，，等概念做出详细的文字以及图示描述。

支配：对于一个图，给定源点，如果从出发到达的所有路径都必须经过点，则称支配，又作。特别的，。
在 dfs 树上能的最深的点称为。
支配树：除源点外，对每个点连一条的边，形成的树即为支配树。对于，，所以可以证明所形成的必为一棵树。
：这是 Lengauer-Tarjan 算法的核心，请读者注意。

对于点，如果存在一条路径，满足路径上的所有点（不含两端）都大于点，则称。对于最小的满足条件的，即。

读者可以结合图示理解跳到的过程：

文字描述：最小的先走向一个大链，再不断向树边或前向边走再跳到一个较轻链，直至到达。满足这个结构的深度最低的点即为。

注：理解的过程中，请紧扣 dfs 树的一个性质——只有前向边和树边可以增加 dfn ，返祖边和横插边都会减小 dfn。

引理

这一部分删去了一些显然的结论，保留了重要的、与证明紧连的结论，后面会进行引用。

引理 1 ：对于任意点，一定是的祖先。
引理 2 ：对于任意点，一定是的祖先。更一般的，如果有点，那么也一定是的祖先。
引理 3 ：对于任意点，一定是的祖先或本身。

考虑已经有两条路，和，所以必须支配，结合引理 1 可得证。
引理 4 ：到的路径一定要经过（左闭右开）链上的点。

证明：
1. ，显然成立。
2. 把分为 3 部分，，，，命名为第一、二、三部分；
  
  属于第一部分，属于第三部分，必然经过。若不经过第二部分，则必有点满足半支配条件，违背了的最小性。

求解

先抄一个公式：

定理 1 ：。

这个定理可以看成一个 DP 过程，即枚举临点转移的过程。

对于前半部分，由于只能经过比大的点，链的起始点只能到为止了。
对于后半部分，即枚举最后一条链的长度，即枚举上一条链是跳到最后一条链的哪一个点的。

其中，后面一种情况的枚举过程可以使用并查集优化，具体见下文代码实现。

求解

方法一

首先需要 DAG 上求支配树的基础，不会的可以去做做 P2597 ZJOI2012] 这道题。

过程：对每个点在 dfs 树上连边，然后跑 DAG 上支配树。

注：作者想了很久，没有想到特别直观的证明方法，如果读者不能理解下文可以先看方法二。

证明：其实就是证明，显然。

，即没有点能通过一条大链到达，故。
，

此时（因为支配树上就挂在下面）。

保证了树边的不可达，保证了假如有点不经过到达，必须要先跳到的链上（引理 4 ）

我们假设这个点为，连接的点为，则满足的条件。根据引理 2 ，一定为的祖先或本身。又根据引理 3 ，从开始就已经挂在下面了，这使一定是在 dfs 树上的祖先了，路径被。

方法二

优雅的解法，下文给出了简洁的证明，也是本文对比其他题解的优势所在。

设是链上最小的点，分类讨论：

若，则。

证明：根据引理 4 ，要到一定要经过链上的点，设到达点，但因为，到达又要经过，，可以用无穷递降法证明不存在。
若，则。

证明： “最小”保证了不会有点从上方跳到，“ ”保证了不会有点从上方跳到。

综上所述，。

可以使用并查集优化。

代码实现

可以参考代码理解。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 200005, MAXM = 300005;

int n, m;
class Graph {
	private : 
	struct edge {
		int to, nex;
	}e[MAXM]; int idx;
	public : 
	int head[MAXN];
	inline void add(int u, int v) {
		e[++ idx].to = v;
		e[idx].nex = head[u];
		head[u] = idx; 
	}
	inline edge operator [] (const int &x) const {
		return e[x];
	}
}G, F, T;
int fa[MAXN], sum[MAXN];
int timer, id[MAXN], dfn[MAXN]; 
int sdom[MAXN], idom[MAXN];
inline void dfs(int u) {
	id[dfn[u] = ++ timer] = u;
	for (int i = G.head[u]; i; i = G[i].nex) {
		int v = G[i].to;
		if (dfn[v]) continue;
		fa[v] = u; dfs(v);
	}
}
struct Dsu {
	int fa[MAXN], mn[MAXN];
	inline Dsu() {
		for (int i = 1; i < MAXN; ++ i)
			fa[i] = mn[i] = i;
	}
	inline int pushll(int x) {
		if (x == fa[x]) return x;
		int tmp = pushll(fa[x]);
		if (dfn[sdom[mn[fa[x]]]] < dfn[sdom[mn[x]]]) mn[x] = mn[fa[x]];
		return fa[x] = tmp;
	}
}d;
vector<int>vec[MAXN];
inline int Calc(int u) {
	sum[u] = 1;
	for (int i = T.head[u]; i; i = T[i].nex) {
		int v = T[i].to;
		sum[u] += Calc(v);
	}
	return sum[u];
}
inline void Solve() {
	dfs(1);
	for (int i = 1; i <= n; ++ i) sdom[i] = i;
	for (int t = timer; t; -- t) {
		int u = id[t];
		for (int v : vec[u]) {
			d.pushll(v);
			if (sdom[d.mn[v]] == u) idom[v] = u;
			else idom[v] = d.mn[v];
		}
		if (t == 1) continue;
		for (int i = F.head[u]; i; i = F[i].nex) {
			int v = F[i].to;
			if (dfn[v] < dfn[sdom[u]]) sdom[u] = v;
			else if (dfn[v] > dfn[u]) {
				d.pushll(v);
				if (dfn[sdom[d.mn[v]]] < dfn[sdom[u]]) sdom[u] = sdom[d.mn[v]];
				
			}
		}
		vec[sdom[u]].push_back(u);
		d.fa[u] = fa[u];
	}
	for (int t = 2; t <= timer; ++ t)
		if (idom[id[t]] != sdom[id[t]])
			idom[id[t]] = idom[idom[id[t]]];
	for (int i = 2; i <= n; ++ i) T.add(idom[i], i);
	Calc(1);
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; ++ i) {
		int u, v; scanf ("%d%d", &u, &v);
		G.add(u, v); F.add(v, u);
	}
	Solve();
	for (int i = 1; i <= n; ++ i)
		printf ("%d ", sum[i]);
	return puts(""), 0;
}

谈支配树

支配树

注例

定义

引理

求解

求解

方法一

方法二

代码实现