支配树 瞎学笔记

poisonous

支配树上支配集，支配树下我和你。（骗人的，支配树跟支配集毛关系没有）

支配树是用来求解有向图必经点问题的算法。

（u1s1 算法的证明根本不体现支配树的本质，学了也是白学，我是强迫症犯了才补上证明的，不要学我）

基础概念

对于一个有向图，选定 \(1\)​​​ 为起点（下文都假定 \(1\) 能到所有点，无自环，不失一般性），对节点 \(x,y\)，\(y\) 支配 \(x\) 当且仅当 \(y\) 是 \(1\to x\) 的必经点，称为 \(x\) 的支配点。不难证明支配关系的自反性、反对称性、传递性。

支配关系还有个类似传递性的神奇性质：若 \(x\neq y\) 都支配 \(z\)，则 \(x,y\) 必有支配关系。若不然，任找一条 \(1\to z\) 简单路径，由支配性知 \(x,y\) 都在上面：若 \(x\) 离 \(1\) 更近，由于 \(x\) 不支配 \(y\)，所以可以从 \(1\) 绕过 \(x\) 到 \(y\) 再到 \(z\)，与 \(x\) 支配 \(z\) 矛盾；\(y\) 更近的情况类似。那么易证（读者自证不难）：任取一条 \(1\to x\) 简单路径，上面所有 \(x\) 的支配点按离 \(1\) 的距离从近到远排列依次为 \(1=x_0\to x_1\to\cdots\to x_s=x\)，则对任意 \(i\in[0,s]\) 知道 \(x_i\) 的所有支配点是 \(x_{0\sim i}\)​​。

称 \(x\) 的所有支配点当中除了自己离自己最近的那个为 \(x\) 的最近支配点，记作 \(idom_x\)，\(idom_1\) DNE。将所有点 \(x\neq 1\) 往 \(idom_x\) 连一条边，得到一棵以 \(1\) 为根的内向树。若不然，必定存在大小大于 \(1\) 的环，由传递性可知存在 \(x\) 支配 \(idom_x\)，与支配关系的反对称性矛盾。这棵树就是原图的支配树。显然，\(x\) 的全部支配点就是它在支配树上的全部祖先，并且排列顺序与在原图任意一条 \(1\to x\) 简单路径中离 \(1\) 的距离从近到远的顺序一致。

支配树的求法

显然，若对每个点 \(x\neq 1\)​​​ 都知道了 \(idom_x\)，那么支配树自然就求出来了。

外向树

显然，以 \(1\) 为根的外向树的支配树就是自己的反图。

DAG

将 DAG 拓扑排序，那么显然，加入一个点对拓扑序在它之前的点的导出子图的支配树并没有影响。所以考虑按拓扑序依次加入，每次只要考虑当前点的最近支配点是谁，插到树上就可以了。

加入点 \(x\)​ 的时候，考虑所有边 \((y,x)\)​，由于是按照拓扑序，所有 \(y\)​ 在之前已经考虑过了。设 \(z\)​ 是所有 \(y\)​ 在支配树上的 LCA，易证有且仅有 \(z\)​ 的所有支配点是 \(x\)​ 的所有支配点，即 \(idom_x=z\)​。

考虑实现。需要实时维护 LCA，考虑树上倍增，每次接一个叶子，确实是可以动态维护倍增数组的，而且很好写，复杂度线对。贴个 P2597 的板子吧。

一般图的 tarjan 算法

一般有向图也是有线对复杂度的求支配树的算法的，叫做 tarjan 算法（Tarjan 老爷子真是 nb，总能发明很难证的算法，而且他自己还总是会证）。虽然 DAG 的特殊求法复杂度跟 tarjan 算法复杂度一样，但是好写的很多，所以 DAG 一般还是写特殊求法。

引入半支配点

找到原图从 \(1\) 出发的一棵 dfs 树（Tarjan 老爷子好像很喜欢 dfs 树耶），不失一般性地，下文认为点 \(i\) 的 dfs 序就是 \(i\)​。对 \(y<x\)，若存在一条 \(y\to x\) 路径满足除端点外全程大于 \(x\)，则称 \(y\) 是 \(x\)​​ 的半支配点。

引理：对 \(x<y\)​，\(x\to y\)​ 的任意一条路径都必定经过它们在 dfs 树上的某个公共祖先。证明：设 \(z=\mathrm{LCA}(x,y)\)​，则把 \(z\)​ 的祖先全删除之后 \(x,y\)​ 所在子树就裂开了，前向边和后向边对连通性屁帮助没有，而横叉边只能是大号点到小号点，所以此时 \(x\)​ 是不能到达 \(y\)​ 的。

跟据引理，不是 \(x\)​​​​ 的祖先的节点 \(y\)​ 一定不是 \(x\)​​ 的半支配点，因为 \(y\to x\)​ 一定经过小于 \(x\)​ 的 \(x\)​ 的祖先（由于 \(y<x\)​，所以 \(y\)​ 不可能是 \(x\)​ 的后代）。

\(x\)​ 的所有支配点也一定是 \(x\)​ 在 dfs 树上的祖先，若不然，删去之后显然可以沿着 dfs 树从 \(1\)​ 走到 \(x\)​。

\(x\)​ 所有支配点都是半支配点的祖先。证明：若存在半支配点 \(y\)​ 是支配点 \(z\)​ 的祖先，则可以先沿 dfs 树 \(1\to y\)​，然后从 \(y\)​ 走一条全程大于 \(x\)​ 的路径到 \(x\)​，自然地绕过了 \(z\)​，与支配性矛盾。

设 \(x\)​ 的 dfs 序最小的半支配点为最远半支配点，记作 \(sdom_x\)​，亦即在 dfs 树上离 \(1\)​ 最近的半支配点。我们有 \(idom_x\leq sdom_x\)​，知道最远半支配点是对最近支配点的一个良好近似，对求最近支配点有帮助。

最远半支配点的求法

对点 \(x\neq 1\)​，枚举所有半支配点到它的路径的一切可能的前驱 \((y,x)\)：

• 若 \(y<x\) 则直接用 \(y\) 更新 \(sdom_x\)。正确性显然，充分性的话，由于 \(y<x\)，所以 \(y\) 只能是半支配点到 \(x\) 的路径的端点。
• 若 \(y>x\)​，设 \(w=\mathrm{LCA}(x,y)\)​，则用树上路径 \(w\to y\)​（掐头留尾）中所有 \(z\)​ 的 \(sdom_z\)​ 来更新 \(sdom_x\)​。证明：首先 \(x=w\)​ 的情况不证自证，下面考虑 \(x\neq w\)​ 的情况。首先想直接用 \(sdom_y\)​ 更新，但它有可能走区间 \((x,y)\)​ 之间的点 \(u\)​ 啊，这就没考虑到。若 \(\mathrm{LCA}(u,y)=w\)​，则跟据引理，由 \(u<y\)​ 知道一旦走到了 \(u\)​，就一定要经过 \(w\)​ 的祖先才能到 \(y\)​，这是一定小于 \(x\)​ 的，所以 \(x\)​ 的半支配点到 \(y\)​ 的路径上小于 \(y\)​ 的只能是 \(w\to y\)​（掐头留尾）中所有的 \(z\)​。设从 \(x\)​ 半支配点走到 \(y\)​ 的路径上第一次交到这条直链上交的是 \(z_0\)​，由于是第一次交上，显然之前走的都大于 \(y\)​，那自然也大于 \(z_0\)​，交上去之后可以直接沿着 dfs 树走到 \(y\)​，最后走到 \(x\)​。所以这个用所有 \(sdom_z\)​​ 的更新方案是既正确又充分的。​​​

通过最远半支配点求最近支配点

对点 \(x\neq 1\)​​​​​，我们设路径 \(p=1\to sdom_x\)​​（留头去尾），\(q=sdom_x\to x\)​​（掐头留尾），\(y\)​​ 是 \(q\)​​ 中最远半支配点最远（亦即 dfs 序最小）的点，显然有 \(sdom_y\leq sdom_x\)​​​​​。分成两种情况：

• 若 \(sdom_y=sdom_x\)​​，则 \(idom_x=sdom_x\)​​。证明：如果 \(sdom_x=1\)​​ 那根据 \(idom_x\leq sdom_x\)​​ 就显然了，下面考虑 \(sdom_x\neq 1\)​​ 的情况。此时显然对任意 \(i,j\)​​，\(p_i\)​​ 不半支配 \(q_j\)​​。假设存在 \(1\to x\)​​ 的不经过 \(sdom_x\)​​​ 的简单路径，由于 \(1\)​​ 不半支配 \(x\)​​，一定经过小于 \(x\)​​ 的点 \(z\)​​。而由于 \(z<x\)​​，跟据引理 \(z\to x\)​​ 必经过 \(fa_x\)​​ 的祖先。如果祖先为 \(q_i\)​​，那就对 \(1\to q_i\)​​ 重新使用上述分析一直到祖先为 \(p_i\)​​ 为止（一定可实现，因为不能经过 \(sdom_x\)​​​ 哦）。然后又可以对 \(p_i\to x\)​​ 重新施加上述分析得到一个新的 \(p_j\)​​，如此往复得到 \(p_k,p_o,\cdots\)。注意到我们考虑的是简单路径，\(p\) 里所有点迟早都会被得到一遍，就不能继续了，而我们的分析是可以一直持续下去的，矛盾。至此我们知道了 \(sdom_x\) 是 \(x\) 的支配点之一，即 \(sdom_x\leq idom_x\)，结合 \(idom_x\leq sdom_x\)​​，得证。

• 若 \(sdom_y<sdom_x\)​，则 \(idom_x=idom_y\)​​​。证明：显然有 \(sdom_x<y\)，由 \(idom_x\leq sdom_x\) 知 \(idom_x<y\)。而若 \(idom_x>idom_y\)，此时 \(idom_x\) 一定不支配 \(y\)（否则 \(idom_y\) 应该调整到 \(idom_x\) 这么近），那么有避开 \(idom_x\) 的路径 \(1\to y\)，再沿 dfs 树走到 \(x\)，与 \(idom_x\) 支配 \(x\) 矛盾。所以一定有 \(idom_x\leq idom_y\)，只要证 \(idom_y\) 支配 \(x\) 则有 \(idom_x=idom_y\)​。

  类似上面，假设存在 \(1\to x\) 的不经过 \(idom_y\) 的简单路径。既然不经过 \(idom_y\) 了，那么直链 \(idom_y\to y\) 上面的点都不能经过了，因为一旦交上去便可沿 dfs 树走到 \(y\)，绕开了 \(idom_y\)，与支配性矛盾。由于 \(idom_y\leq sdom_y,y>sdom_x\)，所以 \(sdom_x\) 以上半支配 \(q\)​​ 的点都不能经过了，剩下来的相当于上面那种情况的局面，可以类似上面无限循环来归谬。

实现

求 \(sdom\)​ 的部分，按 dfs 序从后往前更新显然是无后效性的。查询上开下闭的链上最值怎么维护？树剖？可以巧妙地使用带权并查集（Tarjan 又一次使用自己的成果！），每更新完一个点就把它往父亲合并，易证更新到 \(x\)​ 的时候，\(y\)​ 已经合并到了 \(\mathrm{LCA}(x,y)\)​。​并查集只能路径压缩，不能按秩合并，所以复杂度是一个 \(\log\)。

求 \(idom\) 的部分恰好也涉及上开下闭的链上最值查询，可以窃取之前的并查集成果。但是查询完之后需要更新的 \(idom\) 信息应当是按 dfs 序从前往后更新才是没有后效性的。所以我们可以先把并查集该查的查好存起来（在更新到 \(sdom_x\) 的时候恰好是 \(x\) 的可查状态，可以用

vector

记录 todo-list），结束之后再从前往后扫一遍。

注意点：\(1\) 有可能不能到达所有点，枚举 dfs 序的时候一定是到

nowdfn

instead of

n

。初始化的时候应该把所有点的 dfs 序赋为 \(+\infty\)​，这样在选取「dfs 序最小的半支配点」时比较函数不会出错。

支配树求必经边

珍爱生命，远离抄袭！