支配树原理略解

Zhvv123 · 2022-09-04 17:59:51 · 个人记录

前言

支配树——ZPS——左偏树。

本文内容主要参考 cz_xuyixuan 的博客，笔者在原文的基础上修正了一些表述不清晰的语句，使得内容更容易理解，且增加了自己的部分理解。

简介

对于一个单源有向图上的每个点 w，都存在点 d 满足去掉 d 之后起点无法到达 w，我们称作 d 支配 w，d 是 w 的一个支配点。其中 d 可以是 w 本身和起点。显然，支配关系不会出现大于 1 的环。

对于一个点 w，它支配的所有点构成了它的支配集，所有支配 w 的点构成了它的受支配集。

在支配 w 的点中，如果一个支配点 i\ne w 满足 i 被 w 剩下的所有支配点支配，则这个 i 称作 w 的最近支配点（immediate dominator），记作 idom(w)。显然，起点不存在最近支配点。

• 定理 1：支配 w 的点两两有支配关系，从而除起点以外 idom(w) 是存在且唯一的。

证明：记两个点分别为 u,v，任取一条从起点到 w 的路径，由于 u,v 同时支配 w，所以路径一定同时经过两个点，不妨设先经过的是 u。此时若 u 不支配 v，则存在一条从起点到 v 再到 w 的路径，这与 u 支配 w 相矛盾。

于是，idom(w)\to w 的边构成了一棵树（除了起点之外的点 w 都存在相应的 idom(w)，所以有 n-1 条边；从任意一个点开始跳父亲，最终都会跳到起点，所以一定联通），其中每个点支配它子树中的所有点，它就是支配树。

DAG 上求解

按照拓扑序求解，假设求出了前 i-1 个点的支配树，那么第 i 个点的 idom 即为它的所有前驱在支配树上的 LCA。

正确性证明：

首先，拓扑序的前若干个点建出的支配树一定是整个 DAG 的支配树的子图，因为之后的点不会有边连向之前的点，也就不会影响到之前的结构；

其次，第 i 个点的 idom 一定支配了 i 的所有前驱，所以它一定是这些点在支配树上的公共祖先；

根据最近支配点的定义可知应选择最深的点，即 LCA。

板子推荐：P2597 [ZJOI2012]灾难。

一般有向图上求解

有较为朴素的 O(n^2) 算法：

• 枚举每个点删掉，看其它点是否可达，以此求出每个点的受支配集；

• 再次枚举每个点，它的 idom 即为它的受支配集中除自己外受支配集最大的点。

但是本文重点讲解的是另一个更加 NB 的算法——Lengauer-Tarjan 算法，它可以在 O(n\log n+m) 的时间，O(n+m) 的空间内求出一个一般有向图的支配树。

约定

由于整个算法都是在 dfs 树上进行，下面对于 dfs 树的相关内容进行一些说明：

• 下文通过两个点的 dfs 序来比较它们的大小；

• 树边是属于 dfs 树的边，其余的边为非树边；

前置理论

• 引理 1（路径引理）：对于任意的点 u\leq v，u\rightsquigarrow v 经过 u,v 的公共祖先。

证明：当 u 为 v 的祖先时显然成立；否则 u,v 分别在 LCA 的两棵子树内，若不经过公共祖先，则树边、前向边、后向边都不能跨越子树，横叉边只能连向 dfs 序更小的子树，故必须经过公共祖先。

这个引理可以得到一个简单的推论：只要 u\rightsquigarrow v 上存在 x<v，那么路径上一定存在 y 满足 y\overset +\to v。这个推论非常有用，下面的推理中有时可能会用到，但是可能不会显式地提出。

定义一个点 w 的半支配点 sdom(w) 为除自身以外可以不经过小于 w 的点到达 w 的最小的点。当一个点 v 满足除“最小”以外的限制时，称其为 sdom(w) 的候选。每个点都有半支配点，因为其自身即是候选。

• 引理 2：对于所有 w\ne r，idom(w)\overset +\to w。显然。

• 引理 3：对于所有 w\ne r，sdom(w)\overset +\to w。

证明：首先 fa_w 是一个候选，所以 sdom(w) 不在 w 的子树中，且 sdom(w)\leq fa_w<w，而由路径引理可得 sdom(w)\rightsquigarrow w 必须经过 w 的祖先，只有当 sdom(w) 已经是 w 的祖先时才可能满足半支配点的定义。

• 引理 4：对于所有 w\ne r，idom(w)\overset \centerdot\to sdom(w)。

证明：否则存在一条 r\rightsquigarrow sdom(w) \rightsquigarrow w 的路径不经过 idom(w)。

• 引理 5：对于 u\overset \centerdot\to v，u\overset \centerdot\to idom(v) 或 idom(v)\overset \centerdot\to idom(u)。

证明：否则有 idom(u)\overset +\to idom(v)\overset +\to u\overset \centerdot\to v，而 idom(v) 未成为 idom(u) 说明存在绕过 idom(v) 的路径到 u，而这样就存在不经过 idom(v) 到达 v 的路径：r\rightsquigarrow u\overset \centerdot\to v，矛盾。

从 sdom 到 idom

只用定义显然是无法快速求出 sdom 的，考虑证明如下定理：

• 定理 2：对于任意的 w\ne r，sdom(w)=min\{(v|(v,w)\in E,v<w)\cup (sdom(u)|u>w,\exists(v,w)\in E,u\overset \centerdot\to v) \}

证明：首先两边显然都是 sdom(w) 的候选。当 sdom(w)\to w 时，必定满足左边的限制。否则令 x 为右边，则 sdom(w)\leq x。

考虑一条从 sdom(w) 到 w 的绕过 w 之前的点的路径，令 w 的上一个点是 last，取路径上除两端外满足 p\overset \centerdot\to last 的最小的 p，由于 p 是最小的，所以 sdom(w) 是 sdom(p) 的候选（如果 p 之前的路径上存在 x<p，那么由路径引理可知 x\rightsquigarrow p 上一定存在 p 的祖先，这与 p 是最小的相矛盾），有 sdom(p)\leq sdom(w)。

同时 sdom(p) 还满足右边的条件（p 在绕过 w 之前的点的路径上，所以 p>w，同时 p\overset \centerdot\to last,(last,w)\in E），于是有 x\leq sdom(p)\leq sdom(w)，所以这种情况下有 x=sdom(w)。

现在我们得到了 sdom 的一个替代定义，后面会给出利用这个定义求出所有 sdom 的算法，读者可以思考一下，看看能不能自己想出来。

下面我们将讨论如何利用 sdom 求出 idom。换句话说，相当于找到两者之间的关系。

• 定理 3：对于任意的 w\ne r，如果所有满足 sdom(w)\overset +\to u\overset \centerdot\to w 的 u 也满足 sdom(u)\geq sdom(w)，那么有 idom(w)=sdom(w)。

证明：条件可以写为 sdom(w)\overset \centerdot\to sdom(u)\overset +\to u\overset \centerdot\to w。由引理 4 可知 idom(w)\overset \centerdot\to sdom(w)，所以只需证明 sdom(w) 支配 w 即可。

对与任意 r 到 w 的路径，取上面最后一个小于 sdom(w) 的点 x，在 x 之后的路径上取一个最小的 y 使得 sdom(w)\overset \centerdot\to y\overset +\to w（一定存在，不然 x 就会成为 sdom(w)）。

如果 y\ne sdom(w)，根据条件有 sdom(y)\geq sdom(w)。由于 x 不是 sdom(y)，所以一定存在一个 v 使得 x\overset +\to v\overset +\to y，因为 x 是小于 sdom(w) 的最后一个，所以 v 也满足 sdom(w)\overset \centerdot\to v\overset \centerdot\to w，但是 y 已经是最小的了，矛盾。

于是 y 一定是 sdom(w)，从而所有 r 到 w 的路径都一定经过 sdom(w)，所以 idom(w)=sdom(w)。

• 定理 4：对于任意的 w\ne r，令 u 为所有满足 sdom(w)\overset +\to u\overset \centerdot\to w 的 u 中 sdom(u) 最小的一个，若 sdom(u)\leq sdom(w)，则 idom(w)=idom(u)。

证明：条件可以写为 sdom(u)\overset \centerdot\to sdom(w)\overset +\to u\overset \centerdot\to w。由引理 5 和引理 4 可知 idom(w)\overset \centerdot\to idom(u)，所以只需证明 idom(u) 支配 w 即可。

对与任意 r 到 w 的路径，取上面最后一个小于 idom(u) 的点 x，在 x 之后的路径上取一个最小的 y 使得 idom(u)\overset \centerdot\to y\overset +\to w（一定存在，不然 x 就会成为 sdom(w)）。

由于 y 是最小的，x 又是最后一个小于 idom(u) 的点，所以 x 是 sdom(y) 的候选，sdom(y)\leq x<idom(u)\leq sdom(u)，并且 y 一定不是 sdom(w) 的真后代（否则由于 sdom(y)<sdom(u)，y 将代替 u），从而有 idom(u)\overset \centerdot\to y\overset \centerdot\to sdom(w)。

但是我们注意到存在一条路径 r\overset \centerdot\to sdom(y)\rightsquigarrow y\overset \centerdot\to sdom(w) \overset +\to u，如果 y 不是 idom(u) 的话这就是一条绕过 idom(u) 到达 u 的路径，所以 y 一定是 idom(u)，从而任意一条 r 到 w 的路径都经过 idom(u)，即 idom(u) 支配 w。

这样我们就可以通过 sdom 推出 idom了：

• 对于任意的 w\ne r，令 u 为所有满足 sdom(w)\overset +\to u\overset \centerdot\to w 的 u 中 sdom(u) 最小的一个，则有：

接下来就可以给出算法了。在此之前，读者可以先尝试着思考一下如何用算法来实现。

算法流程

总体上分为 3 步：

• 建出 dfs 树，得到 dfs 序；

• 求出所有点的 sdom；

• 通过 sdom 求出所有点的 idom。

其中 2,3 步是我们重点讨论的。如果之前有过一定的思考，应该可以发现 2,3 步都是可以使用树链剖分 + 线段树解决的，但是那样复杂度不够优秀；若换成 LCT 则常数不够优秀。我们需要一个复杂度和常数均优秀的算法。接下来我们依次考虑第 2 步和第 3 步。

第 2 步

首先，sdom 的替代定义强制我们按照 dfs 序从大到小求解。分析一下，对于一个点 w，我们要枚举它的所有前驱 v，然后查询 v 的祖先中 sdom(u) 最小的点（这里为了涵盖定理 2 左边的情况，可以把 sdom(w) 的初值设成 w），然后取最小值作为 sdom(w)，相当于修改操作。

貌似这个过程并不能优化，但是注意到我们的求解顺序是特殊的，这代表修改操作不断趋近于起点 r，换句话说，已经修改过的点的子树中不会有点再被修改。于是我们只要使用并查集动态维护已经计算过的点构成的森林，然后每个点计算完成后将它与 dfs 树上的父亲合并即可。这个并查集显然可以通过路径压缩来优化，但是按秩合并并不方便，这里不做讨论。

第 3 步

记 v 为满足是 sdom(w) 的儿子且子树中有 w 的点。受到第 2 步算法的启发，考虑将 w 标记在 sdom(w) 上，当计算完一个点 v 之后，将 fa_v 上已经有的标记处理掉，然后清空 fa_v 的标记。

至于如何处理标记，我们先在并查集上查询得到 sdom 最小的 u，若 sdom(u)=sdom(w)，则将 idom(w) 直接设成 sdom(w)；否则有 idom(w)=idom(u)，但是 idom(u) 可能还未求出，所以我们记录 idom(w)=u，最后再从小到大扫一遍，如果一个点 idom(w)\ne sdom(w)，就令 idom(w)=idom(idom(w))，就能求出所有点了。因为按照定义 u 一定不等于 sdom(w)，所以可以区分两种情况。

code

给出 P5180 【模板】支配树 的 代码 作为参考。

例题

Problem 1

CF757F Team Rocket Rises Again。

给定一个 n 个点，m 条边的带权无向图和起点 s。

选择一个点 u（u\ne s），使在图中删掉点 u 后，有尽可能多的点到 s 的最短距离改变（包括 u 本身）。