支配树学习笔记

· · 题解

在我的博客获得不一定更好的体验。

约定：本文中用 u \to v 表示从 u 通过一条边直接走到 v，u \rightsquigarrow v 表示 u 通过某条路径走到 v。

支配关系与支配点

对于一张有向图和一个起始点 s，我们定义 u 支配 v 当且仅当所有 s 到 v 的路径都经过 u，记做 u \mathbin{\mathrm{dom}} v。
方便起见，我们认为 s 可以到达图上每一个点。

若 u \mathbin{\mathrm{dom}} v，则我们认为 u 是 v 的一个支配点。每个点都是自己的支配点，s 是所有点的支配点。

引理 1：支配关系是偏序关系。

根据定义有自反性，反对称性和传递性也是好证的。

引理 2：若 u \mathbin{\mathrm{dom}} w, v \mathbin{\mathrm{dom}} w，则 u \mathbin{\mathrm{dom}} v 或 v \mathbin{\mathrm{dom}} u。

使用反证法，若不满足的话一定不同时满足 u \mathbin{\mathrm{dom}} w, v \mathbin{\mathrm{dom}} w。

支配树

根据上面两个引理，我们可以发现点集和支配关系构成的偏序集的哈斯图构成了一棵以 s 为根的外向树，称之为支配树。

注：一个偏序集 R 的哈斯图是指：对于偏序集中任意两个元素 a, b，当且仅当 a \mathrel{R} b 且不存在 c 使得 a \mathrel{R} c, c \mathrel{R} b 时图上有一条 a 到 b 的边。

对于除 s 以外的任意一个点 u，其都有至少两个支配点。我们称除 u 以外到 u 距离最近的点为 u 的直接支配点，记做 idom(u)。可以发现，idom(u) 就是就是支配树上 u 的父亲。

根据定义可以得到，每个点的支配点是其在支配树上的所有祖先（包括其本身），每个点支配其子树中的所有点。

外向树的支配树

外向树的支配树即为其本身。

DAG 的支配树

引理 3：\forall u, v, u \ne v, u \mathbin{\mathrm{dom}} v \iff \forall w, (w, v) \in E, u \mathbin{\mathrm{dom}} w

证明略。

对于 DAG，我们考虑按拓扑序构造支配树。
对于一个点 u，其支配点集是其所有前驱的支配点集的交加上其本身，对应到支配树上，即为其所有前驱的公共祖先加上其本身，因此点 u 的直接支配点即为其所有前驱在支配树上的 LCA。

Lengauer–Tarjan 算法

Lengauer–Tarjan 算法用于在 O(n \alpha(n)) / O(n \log n) 复杂度内求一张有向图的支配树。该算法引入了半支配点的概念，并通过半支配点来求直接支配点。

首先对原图进行 dfs 求出 dfs 序以及 dfs 生成树 T。
以下定义 u < v \iff dfn _ u < dfn _ v，定义 fa _ u 为 u 在 dfs 树上的父亲。

半支配点

我们定义一个点 u \ne s 的半支配点 sdom(u) 为最小的点 v 使得存在一条路径 v \to v _ 1 \to v _ 2 \to \ldots \to v _ k \to u, \forall i \in [1, k], v _ i > u。

注：在某些地方也称存在一条上述路径的点为半支配点，称同时满足最小的点为最小半支配点。

约定：
以下「满足半支配点的条件」指存在一条上述路径但不一定最小。
以下 u \stackrel{s}{\rightsquigarrow} v 表示 u 到 v 的一条满足 v 的半支配点的条件的路径，u \stackrel{T}{\rightsquigarrow} v 表示 u 通过树边到 v 的路径。
以下讨论中默认点不包括 s。

引理 4：对于任意点 u，sdom(u) < u

证明考虑 fa _ u 一定满足半支配点的条件。

引理 5：对于任意点 u，idom(u) 一定是 u 的祖先。

证明考虑 idom(u) 一定在 T 中从根到 u 的路径上。

引理 6：对于任意点 u，sdom(u) 一定是 u 的祖先。

证明考虑从 sdom(u) 走的第一步只能走到 sdom(u) 的子树中。假设 sdom(u) 不是 u 的祖先，则一定要走到 sdom(u) 的祖先，就矛盾了。

引理 7：对于任意节点 u，idom(u) 一定是 sdom(u) 的祖先（或就是 sdom(u)）。

证明考虑 sdom(u) \stackrel{s}{\rightsquigarrow} u 不经过 T 上 sdom(u) 到 u 这条树链中间的点，因此 sdom(u) 到 u 中间的点一定不是 u 的支配点。

引理 8：对于任意点 u, v，u 是 v 的祖先，要么 u 是 idom(v) 的祖先（或相等），要么 idom(v) 是 idom(u) 的祖先（或相等）。

对于树上任意 idom(u) 到 u 中间的点，一定存在一条路径从 s 出发到 idom(u) 再到 u 再到 v 并不经过这些点，因此要么 idom(v) 是 idom(u) 的祖先，要么 u 是 idom(v) 的祖先。

定理 1：sdom(u) = \min(\{v \mid (v, u) \in E, v < u\} \cup \{sdom(w) \mid w > u \land \exists v > u, (v, u) \in E, \text{s.t. } w\text{ 是 }v\text{ 的祖先或 }w = v\})

证明：设右式的值为 x。

先证 sdom(u) \le x，即证 x 满足成为 sdom(u) 的条件。
若 x 取到第一部分，显然满足。若 x 取到第二部分，则路径 x \stackrel{s}{\rightsquigarrow} w \stackrel{T}{\rightsquigarrow} v \to u 满足条件。

再证 sdom(u) \ge x，相当于证右边的集合一定存在一个元素小于等于 sdom(u)。考虑其对应的路径 sdom(u) \to v _ 1 \to v _ 2 \to \ldots \to v _ k \to u，若 k = 0 则其一定满足 sdom(u) < u, (sdom(u), u) \in E，一定可以被上面式子的第一部分取到。否则 v _ k > u，找到 j 使得 v _ j 是 v _ k 的祖先（或 = v _ k）且 v _ j 最小，只需证 sdom(u) 是一个满足成为 v _ j 的半支配点条件的点，即 \forall i \in [1, j - 1], v _ i > v _ j。我们发现如果存在 v _ i < v _ j，找到最后的 i，可以发现其只能走到子树内的点（因为走到子树外一定要通过返祖边或横叉边，这样会走到一个更小的点，不满足 v _ i 是最后的 < v _ j 的点），因此 v _ i 一定是 v _ j 的祖先，与 v _ j 是 v _ k 在路径中出现的最小的祖先矛盾，所以不存在这样的 v _ i。

综上，sdom(u) \le x 且 sdom(u) \ge x，因此 sdom(u) = x。\square

根据定理 1，我们可以得到一个 O(n \log n) 求半支配点的方法：按 dfs 序从后往前做，对于每个点 u 和他的前驱 v，若 v < u 则用 v 更新 sdom(u)，否则用其 sdom 最小的祖先的 sdom 更新 sdom(u)，后面这部分相当于询问从 v 开始往上的一条树链的 sdom 的最小值，使用带权并查集维护，每扫完一个点就将他与父亲合并即可。

求支配点

方法一：

在 T 基础上加上所有 sdom(u) \to u 的边会形成一个 DAG，其上的支配关系与原图相同，因此在这个图上跑 DAG 的做法即可得到支配树。

证明：显然我们只需要考虑有祖先关系的点。首先容易发现原图存在的支配关系依然存在，然后要证明原图不存在的支配关系在新图上也不存在。
对于一个点 u 及其子树内的一个点 v，如果 u 不支配 v，那么存在一条路径不经过 u 进入 u 的子树内。我们考虑这条路径进入 u 子树前最后一个点 k 和进入后最小的到达的 u 和 v 中间这条树链中的点 r（包括 v 但不包括 u），LCA(u, k) \stackrel{T}{\rightsquigarrow} k \to r 是一条满足 r 的半支配点的路径（可以证明 k \rightsquigarrow r 中的点都 > r），因此如果我们把所有满足半支配点条件的点对作为边全都加入那么支配关系就与原图相同了。而因为一个点所有满足半支配点条件的点都是他的祖先，所以我们只需要保留最上面的一个即可。\square

其实这个做法很好写，因为每个点只会有两个入度而且在 T 上都是他的祖先，所以实际上也不需要拓扑排序直接按 dfs 序做也是对的。

方法二：

但是有人认为上面这个做法太不优雅了，所以这里给出另一种做法。

定理 2：对于任意节点 u，设 v 是 sdom(u) 到 u 这条链上 sdom 最小的点（不包括 u 和 sdom(u)），若 sdom(v) \ge sdom(u)，则 idom(u) = sdom(u)。

证明：等价于证 sdom(u) \mathbin{\mathrm{dom}} u。

对于 sdom(u) = s 显然成立，下面考虑 sdom(u) \ne s 的情况。

假设存在一条到 u 的路径不经过 sdom(u)，记其中最后一个小于 sdom(u) 的点为 x。
我们把树切成五部分，分别是 < sdom(u) 的点（记为第一部分），sdom(u)，u，> sdom(u) 的点（记为第三部分）以及中间的部分（记为第二部分）。显然 x 在第一部分，且 x 要走到第一部分以外的地方只能通过树边或前向边，因此 x 一定是 sdom(u) 的祖先。

考虑 x 之后的路径，一定存在一个 y 使得其在 sdom(u) 到 u 的树链上，因为不存在这样的 y 等价于 x 之后没有进入第二部分，使得 x 满足半支配点的条件且 < sdom(u)，那 sdom(u) 就会变成 x。
我们找到最小的 y，由于 sdom(y) \ge sdom(u) > x，因此从 x 出发到 y 一定要经过 x 到 y 中间这条树链上的点。又因为 x 是最后一个小于 sdom(u) 的点，所以中间这个点一定在 sdom(u) 到 y 中间这条树链上，而这与 y 是最小的在 sdom(u) 到 u 中的点矛盾，因此不存在这样的路径，因此 sdom(u) \mathbin{\mathrm{dom}} u。\square

定理 3：对于任意节点 u，设 v 是 sdom(u) 到 u 这条链上 sdom 最小的点（不包括 u 和 sdom(u)），若 sdom(v) < sdom(u)，则 idom(u) = idom(v)。

证明：因为 idom(u) 是 idom(v) 的祖先（或相等），所以等价于证明 idom(v) \mathbin{\mathrm{dom}} u。

类似地，假设存在一条到 u 的路径不经过 idom(v)，记其中最后一个小于 idom(v) 的点为 x。
同样的分析方法可以得到 x 是 idom(v) 的祖先，在路径上 x 之后一定存在一个 y 使得其在 idom(v) 到 u 的树链上。找到最小的 y。
可以发现这条路径上 x \rightsquigarrow y 是一条满足 y 的半支配点的条件的路径，因此 sdom(y) \le x < idom(v) \le sdom(v)。并且 y 一定不是 sdom(u) 的后代（否则由于 sdom(y) < sdom(v)，与 sdom(v) 最小这点矛盾）因此 idom(v) < y \le sdom(u)。

此时我们发现存在一条路径 s \stackrel{T}{\rightsquigarrow} sdom(y) \stackrel{s}{\rightsquigarrow} y \stackrel{T}{\rightsquigarrow} sdom(u) \stackrel{T}{\rightsquigarrow} v，这条路径不经过 idom(v)，矛盾，因此不存在这样的路径，因此 idom(v) \mathbin{\mathrm{dom}} u。\square

根据上面两个定理，我们可以得到：

idom(u) = \begin{cases} sdom(u) & sdom(v) = sdom(u) \lor sdom(u) = fa _ u \\ idom(v) & \text{otherwise} \end{cases}

在求 sdom 的同时求 idom，具体地，将每个点挂在其 sdom 上，对于第一种情况直接求，对于第二种情况用并查集维护即可。

参考代码

int n, m; // n, m 为点数和边数
struct graph {
    int tot, hd[200005];
    int nxt[300005], to[300005];

    void add(int u, int v) {
        nxt[++tot] = hd[u];
        hd[u] = tot;
        to[tot] = v;
        return ;
    }
} g, fg; // g 为原图，fg 为反图
int timer, fa[200005], dfn[200005], id[200005];
int sdom[200005], idom[200005];
struct dsu {
    int fa[200005], mn[200005];

    dsu() {for (int i = 1; i < 200005; i++) fa[i] = mn[i] = i;}
    int find(int x) {
        if (x == fa[x]) return x;
        int tmp = find(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[200005];

void dfs(int now) {
    id[dfn[now] = ++timer] = now;
    for (int i = g.hd[now]; i; i = g.nxt[i])
        if (!dfn[g.to[i]]) fa[g.to[i]] = now, dfs(g.to[i]);
    return ;
}
void solve() {
    dfs(1);
    for (int i = 1; i <= n; i++) sdom[i] = i;
    for (int i = timer; i >= 1; i--) {
        int u = id[i];
        for (int v : vec[u]) {
            d.find(v);
            if (sdom[d.mn[v]] == u) idom[v] = u;
            else idom[v] = d.mn[v]; // 这里是一个省数组的写法，将 idom 和并查集用同一个数组维护了。
        }
        if (i == 1) continue;
        for (int j = fg.hd[u]; j; j = fg.nxt[j]) {
            if (!dfn[fg.to[j]]) continue;
            if (dfn[fg.to[j]] < dfn[sdom[u]]) sdom[u] = fg.to[j];
            else if (dfn[fg.to[j]] > dfn[u]) {
                d.find(fg.to[j]);
                if (dfn[sdom[d.mn[fg.to[j]]]] < dfn[sdom[u]]) sdom[u] = sdom[d.mn[fg.to[j]]];
            }
        }
        vec[sdom[u]].push_back(u);
        d.fa[u] = fa[u];
    }
    for (int i = 2; i <= timer; i++)
        if (idom[id[i]] != sdom[id[i]]) idom[id[i]] = idom[idom[id[i]]];
    return ;
}

例题

参考资料