P5180 【模板】支配树

Alex_Wei · 2025-02-14 01:48:58 · 题解

注：摘自笔记。所有定理均有通俗易懂的证明，且大量配图。

4. 有向图必经点：支配树

前置知识：有向图 DFS 树。

无向图的必经点由割点和割边刻画，有向图同样存在必经点相关的概念与算法：支配点和支配树。学习一般图支配树能够有效提升图论水平！

4.1 定义与性质

首先明确：接下来的所有探究基于 起点固定 这一前提条件。

对一般有向图 G = (V, E)，选定起点 s。若 s 到 y 的所有路径均经过 x，则称 x 支配 (dominate) y，x 是 y 的 支配点。即 x 是从 s 到 y 的必经点。

对 s 不可达的点讨论支配关系没有意义。不失一般性地，设 s = 1 且 1 可达图上所有点。若有多个起点，建立虚点向这些点连边，转化为起点唯一的情况。

和无向图一样，在讨论支配关系时，只考虑 简单路径。如果重复经过一个点，那么将这两次经过之间的点删去。被删去且没有在新路径上出现的点不是支配点。

支配是一种二元关系，我们记作 D，x 支配 y 可以写成 xDy。从一般二元关系的常见性质出发，探究支配关系所具有的性质：

传递性：若 xDy，yDz，则 1\rightsquigarrow z 的任意路径都经过 y，且 1\rightsquigarrow y 的任意路径都经过 x。因此，x 在 1\rightsquigarrow z 的任意路径上，即 xDz。
自反性：1\rightsquigarrow x 的任意路径都经过 x，即 xDx。
反对称性：若 xDy，yDx，则 1\rightsquigarrow y 的任意路径都经过 x。如果 x\neq y，那么存在 1\rightsquigarrow x 的路径不经过 y，和 yDx 矛盾。因此 x = y。反对称性 即对称性的反面：对称性要求对于任意 x\neq y，若 xDy 则 yDx。

满足以上三条性质的关系称为 偏序关系，元素集合和它对应的偏序关系一起称为偏序集。

补充

偏序关系的含义是 “部分” 满足 “序关系”，即局部满足 全序关系。在全序关系 R 里，元素两两可比较（对 x\neq y，xRy 或 yRx 恰有一个成立）。这种关系抽象成图是一排点，每个点指向它后面的所有点。

直观地，在一个偏序集内部，元素之间通过偏序关系形成很多条链，链与链之间有交叉。在交叉点以外，分别位于两个不同链的元素不能比较。但是单独取出某一条链，上面的元素形成全序集。

对偏序关系建图只能得到 DAG：如果环长大于 1，根据传递性，环上每个点向其它点连边，不满足反对称性。

性质 1

若 xDz 且 yDz，则 xDy 或 yDx。

证明
因为 $xDz$ 且 $yDz$，不妨设 $x$ 在 $y$ 之前，那么 $y$ 不支配 $x$。如果在此基础上 $x$ 不支配 $y$，那么存在一条 $1\rightsquigarrow y\rightsquigarrow z$ 的路径不经过 $x$，与 $xDz$ 矛盾。所以 $xDy$。$\square

当一个偏序关系满足性质 1 时，就可以用树状结构刻画：考虑支配 z 的所有点 D_z = \{x_1, x_2, \cdots, x_k\}，对任意两个不同元素 x_i, x_j 应用该性质，可知元素之间形成了全序关系，所有 x_i 的关系可以用一条链描述。

设 idom_i 表示 D_i 去掉 i 之后被其它所有点支配的点，称为 i 的 直接支配点 (immediate dominator)。特别地，idom_s 没有定义。idom_i 可以理解为 i 的所有支配点当中除了 i 以外距离 i 最近的一个，这里 “最近” 是良定义的：类似无向图两点之间的必经点在它们之间的任意简单路径上出现顺序固定，有向图从起点到某一点之间的必经点在它们之间的任意简单路径上出现的顺序也是固定的。

从 idom_i 向 i 连边，得到 支配树 (dominator tree)，它是一棵叶向树。一个点在支配树上的祖先集合（包括它自己）恰为支配它的所有点。支配树刻画了有向图在给定起点时结点之间的必经关系，类似圆方树刻画了无向图上的必经关系。

4.2 有向无环图

DAG 无环的特殊性质使得我们能够方便地求出其支配树。

拓扑排序。设当前结点为 x。根据拓扑排序的性质，x 对拓扑序在它之前的结点的必经性没有影响，因为 x 不可达它们。因此，只需求出 idom_x。

当 x 只有一条入边 y\to x 时，显然 idom_x = y。到达 x 要走 y\to x 这条边，所以 y 支配 x，由支配的传递性推出 y 在支配树上的所有祖先 anc(y) 都是 x 的支配点，而 y 是距离 x 最近的一个。

当 x 有两条入边 y\to x 和 z\to x 时，若最后一条边是 y\to x，则集合 anc(y) 是必经点；若最后一条边是 z\to x，则集合 anc(z) 是必经点。据定义，x 的支配点是 anc(y) 与 anc(z) 的交集加上 x，前者即 anc(lca(y, z))。因此，idom_x = lca(y, z)。

根据上述分析，容易证明：若 x 有若干条入边 y_i \to x，则 anc(x) \backslash x 等于 \bigcap_{i = 1} ^ k anc(y_i)。所以

idom_x = lca(y_1, y_2, \cdots, y_k)

因为拓扑序在 x 之前的 idom 均已确定，所以在确定每个点的 idom 之后立刻预处理这个点的倍增数组，倍增求 LCA。时间复杂度 \mathcal{O}((n + m)\log n)。

模板题代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1 << 16;
constexpr int K = 16;
constexpr int M = 1e6 + 5;
int p, topo[N], sz[N];
int n, dep[N], deg[N], anc[K][N];
int cnt, hd[N], nxt[M], to[M];
void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
int lca(int u, int v) {
  if(!u || !v) return u | v;
  if(dep[u] < dep[v]) swap(u, v);
  for(int i = K - 1; ~i; i--) {
    if(dep[anc[i][u]] >= dep[v]) u = anc[i][u];
  }
  if(u == v) return u;
  for(int i = K - 1; ~i; i--) {
    if(anc[i][u] != anc[i][v]) {
      u = anc[i][u], v = anc[i][v];
    }
  }
  return anc[0][u];
}
int main() {
  cin >> n;
  for(int i = 1, u; i <= n; i++) {
    scanf("%d", &u);
    while(u) deg[i]++, add(u, i), scanf("%d", &u);
    if(!deg[i]) deg[i] = 1, add(n + 1, i);
  }
  queue<int> q;
  q.push(n + 1), dep[n + 1] = 1;
  while(!q.empty()) {
    int t = q.front();
    q.pop(), topo[++p] = t;
    dep[t] = dep[anc[0][t]] + 1;
    for(int i = 1; i < K; i++) anc[i][t] = anc[i - 1][anc[i - 1][t]];
    for(int i = hd[t]; i; i = nxt[i]) {
      int it = to[i];
      anc[0][it] = lca(anc[0][it], t);
      if(!--deg[it]) q.push(it);
    }
  }
  for(int i = p; i; i--) {
    int id = topo[i];
    sz[anc[0][id]] += sz[id] + 1;
  }
  for(int i = 1; i <= n; i++) printf("%d\n", sz[i]);
  return 0;
}

4.3 一般图

先考虑朴素做法。和无向图的必经性一样，我们删掉 x 后检查 s 是否可达 y，由此判断 x 是不是 y 的支配点。因此，独立地删掉每个点 x\neq s，剩余的图上所有 s 不可达的点被 x 支配。时间 \mathcal{O}(nm)。

Thomas Lengauer 和 Robert Tarjan 于 1979 年给出了更快的支配树算法。具体多快呢？\mathcal{O}(m\log n)。精细实现可以做到几乎线性的 \mathcal{O}(m\alpha(m, n))。

首先求出以 s 为根的 DFS 树，将每个点重新编号为它的时间戳。因为可以只走树边，所以每个点的直接支配点是它在树上的真祖先（祖先且不相等）。

引理 1

在研究强连通分量横叉边的性质的时候，一个基本结论是如果 v < u，那么 v 可达 u 当且仅当 v 可达 d，其中 d = lca(u, v)。接下来的引理和这个结论密切相关。

引理 2

如果 v < u，那么所有 v 到 u 的路径都经过 d 的祖先。

证明

在考虑 DFS 树的时候，一个形象的方法是把儿子按 DFS 顺序从左到右排列。这样，对于两个没有祖先后代关系的点，左边的点的时间戳小于右边的点。

这个引理的一句话证明是，因为只有树边或前向边增加编号，所以从小于 u 的点走到不小于 u 的点这一步 x\to y 是树边或前向边，那么 x 是 u 的祖先（如果 x < u 且 x 不是 u 的祖先，那么 x 子树内所有点都小于 u），而从 v 开始走到某个 u 的祖先的过程中，u, v 的 LCA 只会不断变浅。

如上图，v = 6，u = 7，虚线是非树边。从 u 走到某个 d = 5 的祖先 1 之前的路径用红色标出，之后的路径用蓝色标出。绿色是编号大于 u 的点，可以发现能够直接走到它们的编号不大于 7 的点只有 7 的祖先。红色路径上每个点和 7 的 LCA 依次是 5, 1, 1，这个 LCA 只会变得越来越浅。

具体地，设 c 是当前 u 和 v 的 LCA，初始为 d，当 v = c 时停止。从 v 出发依次考虑路径上的每一步：

如果走树边或前向边，那么 c 不变。

如果走返祖边且没有停止，那么 c 不变。

如果走横叉边，那么 c 只会变成 c 的祖先，因为能够使得 c 变深的 v' > v，但横叉边只会减小时间戳。例如上图中不会出现 2, 3 或 4 到 6 的使得和 7 的 LCA 变深的横叉边。

所以最终的 c 是 d 的祖先，路径一定经过 d 的祖先。\square

引理 2 是有向图上路径的强有力而不那么平凡的结论。它可以想象成一个单向的 “屏障”，从 x 左边到 x 右边必须要经过这个屏障上的点，从 x 右边到 x 左边则不需要。

考虑 1 到 x 的任意路径。如果经过了小于 x 但不是 x 的祖先的点，那么根据引理 2，之后一定会经过 x 的祖先。我们考虑最后一个这样的祖先 d，之后只会经过大于 x 的点到 x。因此，d 可以只经过大于 x 的点到 x。如果有很多个这样的祖先，显然只有最浅的祖先对支配关系是有用的。这个概念比较关键，我们给它一个定义：

半支配点

存在路径 u\to p_1 \to \cdots \to p_k \to x 且 p_i > x 的最小的 x 的祖先 u 称为 x 的 半支配点 (semidominator)，记为 sdom_x。

将上述定义的 “x 的祖先” 的限制去掉没有影响，因为如果 u < x 且 u 不是 x 的祖先，那么根据引理 2，路径经过 x 的祖先 d < u。

为方便描述，对 u < v，我们称 u 到 v 的路径是 好路径，当且仅当中途只经过大于 v 的点。

已知 idom_x 和 sdom_x 都是 x 的祖先，那么自然地，我们希望确定它们的位置关系。这个也很显然：因为 sdom_x 可以绕过 sdom_x 到 x 的树上路径到达 x，所以这段路径上的点（不含 sdom_x）都不可能支配 x。

如上图，sdom_4 = 2，idom_4 = 1。3 不可能是支配点，因为根据 sdom 的定义，存在一条 2 到 4 且中途只经过大于 4 的点的路径 2\to 5\to 4 绕过了它。但是从 1 出发又可以绕过 2 到 4，所以 2 也不是支配点。

引理 3

引理 3 可以理解为 sdom_x 到 x “跳过” 了一些点，这些点不可能成为 x 的支配点。引理 3 带给我们的启发是任何这样的 (sdom_u, u) 二元组都能够让我们 “跳过” 一些点。

具体地，idom_x 和 sdom_x 都在 x 到根的路径上。我们把这条链拿出来水平摆放，1 在最左边，x 在最右边，那么每个 sdom_u 到 u（u 在链上）都会跳过一些点，这些点不可能是 x 的支配点，因为可以从 1 在链上走到 sdom_u，然后根据 sdom 的定义只经过大于 u 的点（于是不经过被跳过的点）到 u，再从链上走到 x。

以上分析表明被二元组跳过的点一定不是支配点。那么没有被任何二元组跳过的点是否一定是支配点呢？

引理 4

对 x 的真祖先 y，如果不存在 x 的祖先 u 使得 y 落在 sdom_u 到 u 在树上的路径上（不含两端），那么 y 支配 x。

证明

假设存在 1 到 x 的不经过 y 的路径。考虑路径上所有 x 的祖先，可知存在 u 到 v 的路径 P，使得路径上不经过其它 x 的祖先，其中 u, v 都是 x 的祖先且 u 是 y 的真祖先，v 是 y 的真后代。

假设 P 中途经过了小于 v 的点，那么根据引理 2，P 在此之后经过了 v 的真祖先，和 P 不经过其它 x 的祖先矛盾。于是 P 是好路径。因此 sdom_v \leq u。因为 u 是 y 的真祖先，所以 sdom_v 是 y 的真祖先，和 y 不落在任何 sdom_u 到 u 之间矛盾。\square

如上图，蓝色是从 u 出发跳过 y 的好路径，红色是从 u 出发经过 z < v 所以最终一定经过 lca(z, v)（x 的小于 v 的祖先）的路径。

引理 3 和引理 4 合起来告诉我们一个重要结论：y 支配 x 当且仅当 y 没有被覆盖。具体地，用 x 的所有祖先 u 的 sdom_u 到 u（不含两端）覆盖 1 到 x 的链，那么最深的没有被覆盖的 x 的真祖先就是 idom_x。这个显然可以 DP。

一个等价表述是仅保留树边和 sdom_x 到 x 的边不影响支配关系。于是可以使用 DAG 支配树的做法。

设 sdom_x 到 x 从左到右分别覆盖了 p_1, \cdots, p_k。如果这些点的 sdom 都在 sdom_x 及其右边，那么 sdom_x 就没有被覆盖。否则 idom_x 在 sdom_x 左边。

称添加一个点 u 表示用 sdom_u 到 u 覆盖。考虑使得 sdom_{p_i} 最小的 p_i，那么在添加 p_{i + 1}, \cdots, p_k, x 时，只会影响到 sdom_{p_i} 及其右边。假设现在已经添加了 1 到 p_i 的每个点，那么此时最深的未被覆盖的 p_i 的真祖先 idom_{p_i} 在 sdom_{p_i} 或其左边，而添加 p_{i + 1}, \cdots, p_k, x 不会让 idom_{p_i} 被覆盖，且覆盖了 p_{i\sim k}。于是此时最深的未被覆盖的 x 的真祖先依然是 idom_{p_i}。综上所述：

结论 1
idom_x = \begin{cases} sdom_x, & \forall p_j : sdom_x \leq sdom_{p_j}; \\ idom_{p_i}, & \exists p_i :(\forall p_j : sdom_{p_i}\leq sdom_{p_j}) \land sdom_{p_i} < sdom_x. \end{cases}

如上图，红色的 idom_{p_i}（可能和 sdom_{p_i} 相等）不会被 p_j(j > i) 和 x 覆盖，而蓝色的 p_{i\sim k} 又被 x 覆盖，所以 idom_x = idom_{p_i}。

具体如何实现呢？只需计算 sdom_x 到 x 在树上的所有点（不含 sdom_x）的 sdom 的最小值。这种两端具有祖先后代关系的链上最值查询有很经典的做法：把查询挂到较浅的端点处，在 DFS 回溯时维护子树内每个点到当前点的链上最值并回答对应的询问，带权并查集即可。具体地，在并查集内额外维护每个点到它指向结点的树上路径的点权最小值，回溯时让当前点的所有儿子在并查集内指向当前点即可。

现在还要求 sdom。我们考虑从 u 到 x 的好路径。没有中间点的情况是容易处理的，因为此时 u 到 x 就是一条树边或前向边，只需求出指向 x 的 u 最小的前向边即可。

如果有中间点，那么根据 DP 的思想，自然地考虑路径的最后一条边 v\to x。但是这里有个问题，就是路径上 u 到 v 的部分不一定是好路径，而只用 sdom_v 更新 sdom_x 显然没有考虑到这种情况。

设中途经过的最小点是 y，那么 x < y \leq v。如果 y 不是 v 的祖先，那么根据引理 2，y 到 v 一定会经过 lca(y, v) < y，矛盾。因此 y 是 v 的祖先，也就是说，y 落在 lca(x, v) 到 v 在树上的路径上（不含 lca(x, v)）。而 y 又是中途经过的最小的点，所以路径上 u 到 y 的部分是好路径。

对于每条边 v\to x，考虑用 lca(x, v) 到 v 在树上的所有点（不含 lca(x, v)）的 sdom 更新 sdom_x。因为任何 u 到 x 的最后一条边是 v\to x 的好路径，都给出了 u 到 y 的好路径，所以不会漏情况，把 sdom_x 算大。而任何 u 到 y 的好路径都可以扩展（从树边走到 v，再走 v\to x）得到一条 u 到 x 的好路径，所以不会多情况，把 sdom_x 算小。

结论 2
sdom_x = \min(\{u \mid u < x \land (u, x) \in E\} \cup \{sdom_y \mid y > x \land \exists u : (y\in anc(u) \land (u, x) \in E\}))
其中 anc(u) 表示 u 的祖先集合。

如上图，蓝色边 u_1\to x 对应的 y 用蓝色标出，红色边 u_2\to x 对应的 y 用红色标出。

后半部分怎么算呢？和 idom 一样，依然是具有祖先后代关系的链最值查询，使用带权并查集维护即可。不过显然地，这两部分可以共用一个带权并查集。

时间复杂度是并查集 n 次合并 m 次查询。模板题代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int n, m, dn, fa[N], ind[N], dfn[N];
int sdom[N], idom[N], sz[N];
vector<int> e[N], rev[N], buc[N];
void dfs(int id) {
  ind[dfn[id] = ++dn] = id;
  for(int it : e[id]) if(!dfn[it]) fa[it] = id, dfs(it);
}
struct dsu {
  int fa[N], mi[N]; // mi 维护 sdom 最小的点的编号
  int find(int x) {
    if(fa[x] == x) return fa[x];
    int f = fa[x];
    fa[x] = find(f);
    if(sdom[mi[f]] < sdom[mi[x]]) mi[x] = mi[f];
    return fa[x];
  }
  int get(int x) {
    return find(x), mi[x];
  }
} tr;
int main() {
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    rev[v].push_back(u);
  }
  dfs(1), sdom[0] = n + 1;
  for(int i = 1; i <= n; i++) tr.fa[i] = i;
  for(int i = n; i; i--) { // i = 1 的时候有些语句不用执行, 不过执行了也没事
    int id = ind[i];
    for(int it : buc[i]) idom[it] = tr.get(it); // 此时的 idom 是 sdom 最小的 pi
    if(i == 1) break;
    sdom[id] = i;
    for(int it : rev[id]) {
      if(dfn[it] <= i) sdom[id] = min(sdom[id], dfn[it]);
      else sdom[id] = min(sdom[id], sdom[tr.get(it)]);
    }
    tr.mi[id] = id, tr.fa[id] = fa[id]; // 连接 id 和 fa[id]
    buc[sdom[id]].push_back(id); // 把询问挂到对应位置
  }
  for(int i = 2; i <= n; i++) {
    int id = ind[i];
    if(sdom[idom[id]] != sdom[id]) idom[id] = idom[idom[id]]; // 如果 sdom 最小的 sdom[pi] 不等于 sdom[id], 那么 idom[id] = idom[pi]
    else idom[id] = sdom[id]; // 否则 idom[id] = sdom[id]
  }
  for(int i = n; i; i--) {
    int id = ind[i];
    sz[i] += 1;
    if(i > 1) sz[ind[idom[i]]] += sz[i];
  }
  for(int i = 1; i <= n; i++) cout << sz[i] << " ";
  cout << "\n";
  return 0;
}