Warning: session_start(): open(/tmp/sess_852d69ae4baa6e0f5d6291ab559417c4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 支配树学习笔记 =====
给一个有向图 $G=$，给定一个起点 $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_uw>x$，因此这条路径在 $G$ 中没有经过 $x$。
$G$ 中 $x$ 不支配 $y\Rightarrow G'$ 中 $x$ 不支配 $y$：
存在一条路径 $1\to\cdots\to y$ 不经过 $x$。考虑抽出这条路径上所有为 $y$ 祖先的点，那么一定存在相邻的两个点，第一个 $x$。不妨设为 $zu$，考虑一条符合要求的路径，设路径上第一次出现的 $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$。不妨设为 $x<\text{idom}(v)