===== 支配树学习笔记 =====

给一个有向图 $G=<V,E>$，给定一个起点 $s$，对于两点 $x,y$，若删去 $x$ 后，$s$ 不能到达 $y$，那么 $x$ 是 $y$ 的支配点。$s$ 和 $y$ 是两个平凡的支配点。

支配点之间形成了一棵树的关系，称为支配树。

**定理 1**：支配关系形成一棵树。

**证明**：假设 $x,y$ 是 $z$ 的支配点，那么必然有一条简单路径为 $s\to x\to y\to z$ 或 $s\to y\to x\to z$ 的形式，不妨设为前者。若 $x$ 不是 $y$ 的支配点，那么就存在路径 $s\to y\to z$，其中 $s\to y$ 不经过 $x$，$y\to z$ 也不经过 $x$（因为是简单路径），与 $x$ 支配 $z$ 矛盾。因此 $z$ 的所有支配点之间也两两相互支配，形成树关系。$\Box$

==== 有根树的支配树 ====

显然是它本身。

==== DAG 的支配树 ====

考虑按拓扑序构建，加入点 $u$ 时，它的所有入点已经在支配树中了，显然这些点在支配树上的 LCA 是 $\text{idom}(u)$。

==== 半支配点 ====

考虑一般的有向图，以 $s$ 为根任意建一根 dfs 树，为了方便，不妨用 dfn 对点重编号。

定义 $u$ 的半支配点 $\text{sdom}(u)=\min\{v|\exists v\to v_{1}\to\cdots\to v_{t}\to u,v_{1},\cdots,v_{t}>u\}$，即所有满足下面条件的点 $v$ 中的最小点：存在一条从 $v$ 到 $u$ 的路径，使得路径上除 $u,v$ 外的所有点都大于 $u$。

除根之外，半支配点唯一存在，因为 $u$ 在 dfs 树上的父亲满足条件，且半支配点取最小的那个。

**定理 2**：$u$ 的半支配点一定是 $u$ 的祖先。

**证明**：假设 $v:=\text{sdom}(u)$ 不是 $u$ 的祖先。由于 $fa_u<u$，因此 $v<u$。因此在 dfs 树建树的过程中，由于 $v$ 能到达 $u$，$u$ 一定在 $v$ 的子树中，矛盾。$\Box$

**定理 3**：将图中所有非树边删去，加连 $\text{sdom}(u)\to u$ 后，支配点不变。

**证明**：设新图为 $G'$。

$G'$ 中 $x$ 不支配 $y\Rightarrow G$ 中 $x$ 不支配 $y$：

一定存在一条路径 $1\to\cdots\to z\to w\to\cdots\to y$，其中 $z<x<w\le y$ 且依次为祖先关系。由于 $z\to w$ 是 $G'$ 上的非树边，因此一定有 $z=\text{sdom}(w)$。因此在 $G$ 中 $z$ 到 $w$ 存在一条路径，中间的每个点 $>w>x$，因此这条路径在 $G$ 中没有经过 $x$。

$G$ 中 $x$ 不支配 $y\Rightarrow G'$ 中 $x$ 不支配 $y$：

存在一条路径 $1\to\cdots\to y$ 不经过 $x$。考虑抽出这条路径上所有为 $y$ 祖先的点，那么一定存在相邻的两个点，第一个 $<x$，而第二个 $>x$。不妨设为 $z<x<w\le y$。这条路径上 $z$ 到 $w$ 中间都不是 $y$ 的祖先，当然也不是 $w$ 的祖先。假设这其中存在一个点 $<w$，那么与前面类似，这个点在 dfs 时应当是 $w$ 的祖先，矛盾。从而 $\text{sdom}(w)\le z$，因而 $1\to\cdots\to\text{sdom}(w)\to w\to\cdots\to y$ 是 $G'$ 的一条不经过 $x$ 的路径。$\Box$

注意到 $G'$ 是一个 DAG，因此可以在 $\mathcal{O}(n\log n)$ 的时间内求出支配树。

下面讨论半支配点的求法。首先证明一个引理，对于 $u<v$，$u$ 到 $v$ 的任意路径上一定经过 $v$ 的祖先。

**证明**：假设不经过，前向边和横叉边都使得 $u$ 减小，树边和后向边只能往子树走，由于这个 $u$ 不是 $v$ 的祖先，因此 $u$ 的整个子树都 $<v$。因此 $u$ 永远走不到 $v$，矛盾。$\Box$

考虑枚举 $u$ 的半支配点路径上前面一个结点 $v$，即枚举 $u$ 的所有入边。若 $v<u$，那么路径只能是 $v\to u$，$\text{sdom}(u)=\min\{\text{sdom}(u),v\}$。

若 $v>u$，考虑一条符合要求的路径，设路径上第一次出现的 $v$ 的祖先为 $w$。显然路径一直到 $w$ 的过程中都大于 $w$，否则与引理矛盾。因此该路径满足 $w$ 的要求。而对于所有 $v$ 的大于 $\text{LCA}(u,v)$ 的祖先，它们的半支配点显然也满足 $u$。因此用它们更新 $\text{sdom}(u)$ 可以找到最优值。

==== 支配点 ====

定义 $\text{idom}(u)$ 为 $u$ 在支配树上的父亲。

$u$ 的支配点都是 $u$ 的祖先。显然 $\text{sdom}(u)$ 到 $u$ 之间的点不会是 $u$ 的支配点，所以 $\text{idom}(u)$ 是 $\text{sdom}(u)$ 的祖先。

**定理 4**：若 $v$ 是 $u$ 的祖先，要么 $\text{idom}(v)\ge\text{idom}(u)$，要么 $v\le\text{idom}(u)$。

**证明**：假设 $\text{idom}(v)<\text{idom}(u)<v<u$，注意到 $\text{idom}(u)$ 不是 $v$ 的支配点，因此存在一条 $1$ 到 $v$ 的路径不经过 $\text{idom}(u)$，矛盾。$\Box$

下面讨论支配点的求法。

定义 $S(u)$ 表示 $\text{sdom}(u)$ 到 $u$ 的所有结点（不含 $\text{sdom}(u)$）。记 $v$ 为 $S(u)$ 中 $\text{sdom}$ 最小的点。

若 $\text{sdom}(v)=\text{sdom}(u)$，那么有 $\text{sdom}(u)$ 是 $u$ 的支配点。否则，使用定理 3 类似的方法可以证明 $\text{sdom}(u)<\text{sdom}(u)$。由定理 4 可知 $\text{idom}(u)=\text{sdom}(u)$。

若 $\text{sdom}(v)<\text{sdom}(u)$，那么有 $\text{idom}(v)\le\text{sdom}(v)<\text{sdom}(u)<v<u$。定理 4 中，$v\le\text{idom}(u)$ 显然不成立，因此 $\text{idom}(v)\ge\text{idom}(u)$。

假设存在一条 $1\to u$ 的路径不经过 $\text{idom}(v)$，那么它不能经过 $\text{idom}(v)$ 到 $v$ 中的任意点。考虑抽出这条路径上所有为 $u$ 祖先的点，那么一定存在相邻的两个点，第一个 $<\text{idom}(v)$，而第二个 $>v$。不妨设为 $x<\text{idom}(v)<v<z\le u$。这条路径上 $x$ 到 $z$ 中间都不是 $u$ 的祖先，当然也不是 $z$ 的祖先。假设这其中存在一个点 $<z$，那么与前面类似，这个点在 dfs 时应当是 $z$ 的祖先，矛盾。从而 $\text{sdom}(z)\le x<\text{idom}(v)\le\text{sdom}(v)$。这与 $v$ 的最小性矛盾。因此 $\text{idom}(v)$ 是 $u$ 的支配点，从而 $\text{idom}(u)=\text{idom}(v)$。

==== 实现 ====

求 $\text{sdom}$ 时，从大到小维护每个点，计算完某个点后把它和它的所有孩子连接起来。