题解：P5180 【模板】支配树

# 支配树 作者写这篇文章的原因主要是现有题解要么就毫无证明，要么证明过程不太直观、概念不太清晰，在我的学习过程中困扰了我很久。 我是农历年前学的，由于实力比较弱，那时候经常坐在房间椅子上一个下午想这个算法，勉强看懂证明后草草放弃。这几天回想到这个算法，仔细思考想清楚了之后决定写下本文，方便给像我这样的学习者一个向导。 言归正传，由于作者我之前主要是根据 [这篇巨佬的文章](https://www.luogu.com.cn/article/8lpy3e1e) 学习的，因此在表示和论述方法上会有相似，但是证明过程和内容编排多数为自己的想法，使用了更感性的证明论述方法。如果您学术目的比较强，也可以去参考那篇文章。 ## 注例 这里给出了一些本文符号代表的含义，读者不理解时可以来这里检索。 - 在本文中，使用 $u$ 代指 $dfn[u]$ ，关于 $u$ 的比较即为 $dfn$ 的比较。 - 文章中用 $u\overset{T}{\rightsquigarrow}v$ 表示 $u$ 到 $v$ 在 dfs 树上的路径，用 $u\overset{S}{\rightsquigarrow}v$ 表示在图上的路径。 - 本文中的 $lca$ 以及 $dep$ 默认指支配树上的 $lca$ / $dep$ ，如果指 dfs 树上的 $lca$ 会写作 $lca_T$ 。 ## 定义 作者自己学习过程中的一大难点就是没有抓住准确的定义，经过摸索猜测联系下文等才理解。 这一部分会对支配，支配树， $dom$ ， $idom$ ， $sdom$ 等概念做出详细的文字以及图示描述。 - 支配 ： 对于一个图 $G=\{V,E\}$ ，给定源点 $S$ ，如果从 $S$ 出发到达 $u$ 的所有路径都必须经过点 $v$ ，则称 $v$ 支配 $u$ ，又作 $v\ dom\ u$ 。特别的， $S\ dom\ u$ 。 - 在 dfs 树上能 $dom\ u$ 的最深的点称为 $idom(u)$ 。 - 支配树 ： 除源点外，对每个点 $u$ 连一条 $(idom(u),u)$ 的边，形成的树即为支配树。对于 $u\neq S$ ，$idom(u) \neq u$ ，所以可以证明所形成的必为一棵树。 - $sdom$ ： 这是 Lengauer-Tarjan 算法的**核心**，请读者**注意** 。 对于点 $w$ ，如果存在一条路径 $w\overset{S}{\rightsquigarrow}u$ ，满足路径上的所有点（不含两端）都大于点 $u$ ，则称 $w\ sdom\ u$ 。对于最小的满足条件的 $w$ ，即 $sdom(u) = w$ 。 读者可以结合图示理解 $sdom(u)$ 跳到 $u$ 的过程 ：  文字描述：最小的 $sdom(u)$ 先走向一个大链，再不断向树边或前向边走再跳到一个较轻链，直至到达 $u$ 。满足这个结构的深度最低的点即为 $sdom(u)$ 。 注：理解 $sdom$ 的过程中，请紧扣 dfs 树的一个性质——只有前向边和树边可以增加 dfn ，返祖边和**横插边**都会减小 dfn。 ## 引理 这一部分删去了一些显然的结论，保留了重要的、与证明紧连的结论，后面会进行引用。 - 引理 1 ： 对于任意点 $u$ ， $idom(u)$ 一定是 $u$ 的祖先。 - 引理 2 ： 对于任意点 $u$ ， $sdom(u)$ 一定是 $u$ 的祖先。更一般的，如果有点 $w\ sdom\ u$ ，那么 $w$ 也一定是 $u$ 的祖先。 - 引理 3 ： 对于任意点 $u$ ， $idom(u)$ 一定是 $sdom(u)$ 的祖先或本身。 考虑 $sdom(u)$ 已经有两条路， $sdom(u)\overset{T}{\rightsquigarrow}u$ 和 $sdom(u)\overset{S}{\rightsquigarrow}u$ ，所以 $idom(u)$ 必须支配 $sdom(u)$ ，结合引理 1 可得证。 - 引理 4 ： $S$ 到 $u$ 的路径一定要经过 $sdom(u)\overset{T}{\rightsquigarrow}u$ （左闭右开）链上的点。 证明 ： 1. $sdom(u) = S$ ，显然成立。 2. 把 $T$ 分为 3 部分， $[S,sdom(u))$ ， $[sdom(u), u)$ ，$[u, n]$ ，命名为第一、二、三部分； $S$ 属于第一部分， $u$ 属于第三部分，必然经过。若不经过第二部分，则必有点 $v \in [S,sdom(u))$ 满足半支配条件，违背了 $sdom(u)$ 的最小性。 ## 求解 $sdom(u)$ 先抄一个公式 ： - 定理 1 ： $sdom(u)=min(\{v|(v,u)\in E,v<u\}\cup\{sdom(w)|w>u\land\exists v>u,(v,u)\in E,s.t.\ w是v的祖先或w=v\})$ 。 这个定理可以看成一个 DP 过程，即枚举临点转移的过程。 1. 对于前半部分，由于 $sdom(u)\overset{S}{\rightsquigarrow}u$ 只能经过比 $u$ 大的点，链的起始点只能到 $v$ 为止了。 2. 对于后半部分，即枚举最后一条链的长度，即枚举上一条链是跳到最后一条链的哪一个点的。 其中，后面一种情况的枚举过程可以使用并查集优化，具体见下文代码实现。 ## 求解 $idom(u)$ ### 方法一 首先需要 DAG 上求支配树的基础，不会的可以去做做 [P2597 ZJOI2012\] ](https://www.luogu.com.cn/problem/P2597) 这道题。 过程 ： 对每个点 $u\neq S$ 在 dfs 树上连边 $(sdom(u),u)$ ，然后跑 DAG 上支配树。 注：作者想了很久，没有想到特别直观的证明方法，如果读者不能理解下文可以先看方法二。 证明 ： 其实就是证明 $idom(u)=lca(sdom(u),fa_u)$ ，显然 $dep_{sdom(u)} \ge dep_{fa_u}$ 。 1. $sdom(u)=fa_u$ ，即没有点能通过一条大链到达 $u$ ，故 $idom(u)=fa_u$ 。 2. $sdom(u) < fa_u$ ， 此时 $lca(sdom(u), fa_u)=lca(sdom(u),idom(fa_u))$ （因为支配树上 $fa_u$ 就挂在 $idom(fa_u)$ 下面）。 $idom（fa_u)$ 保证了树边的不可达， $sdom(u)$ 保证了假如有点不经过 $lca$ 到达 $u$ ，必须要先跳到 $sdom(u)\overset{T}{\rightsquigarrow}u$ 的链上（引理 4 ）。 我们假设这个点为 $y$ ， $y$ 连接的点为 $r$ ，则 $lca_T(sdom(u),r)$ 满足 $y$ 的 $sdom$ 条件。根据引理 2 ， $sdom(y)$ 一定为 $lca_T$ 的祖先或本身。又根据引理 3 ， $y\overset{T}{\rightsquigarrow}u$ 从 $y$ 开始就已经挂在 $idom(y)$ 下面了，这使 $lca(sdom(u),idom(fa_u)$ 一定是 $lca_T(sdom(u),r)$ 在 dfs 树上的祖先了，路径被 $dom$ 。 ### 方法二 优雅的解法，下文给出了简洁的证明，也是本文对比其他题解的优势所在。 设 $v$ 是 $sdom(u)\overset{T}{\rightsquigarrow}u$ 链上 $sdom$ 最小的点，分类讨论 ： 1. 若 $sdom(v) \ge sdom(u)$ ，则 $idom(u)=sdom(u)$ 。 证明 ： 根据引理 4 ， $S$ 要到 $u$ 一定要经过 $sdom(u)\overset{T}{\rightsquigarrow}u$ 链上的点，设到达点 $r$ ，但因为 $sdom(r)\ge sdom(u)$ ，到达 $r$ 又要经过，$sdom(u)\overset{T}{\rightsquigarrow}r$ ，可以用无穷递降法证明 $r$ 不存在。 2. 若 $sdom(v) \ge sdom(u)$ ， 则 $idom(u)=idom(v)$ 。 证明 ： “最小”保证了不会有点从 $idom(v)$ 上方跳到 $sdom(u)\overset{T}{\rightsquigarrow}u$ ，“ $idom$ ”保证了不会有点从 $idom(v)$ 上方跳到 $idom(v)\overset{T}{\rightsquigarrow}sdom(u) \in idom(v)\overset{T}{\rightsquigarrow}v$ 。 综上所述，$ idom(u) = \begin{cases} sdom(u) & \text{} sdom(v) = sdom(u) \land v=fa_u\\idom(v) & \text{otherwise}\end{cases} $ 。 可以使用并查集优化。 ## 代码实现 可以参考代码理解。 ```cpp #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 200005, MAXM = 300005; int n, m; class Graph { private : struct edge { int to, nex; }e[MAXM]; int idx; public : int head[MAXN]; inline void add(int u, int v) { e[++ idx].to = v; e[idx].nex = head[u]; head[u] = idx; } inline edge operator [] (const int &x) const { return e[x]; } }G, F, T; int fa[MAXN], sum[MAXN]; int timer, id[MAXN], dfn[MAXN]; int sdom[MAXN], idom[MAXN]; inline void dfs(int u) { id[dfn[u] = ++ timer] = u; for (int i = G.head[u]; i; i = G[i].nex) { int v = G[i].to; if (dfn[v]) continue; fa[v] = u; dfs(v); } } struct Dsu { int fa[MAXN], mn[MAXN]; inline Dsu() { for (int i = 1; i < MAXN; ++ i) fa[i] = mn[i] = i; } inline int pushll(int x) { if (x == fa[x]) return x; int tmp = pushll(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[MAXN]; inline int Calc(int u) { sum[u] = 1; for (int i = T.head[u]; i; i = T[i].nex) { int v = T[i].to; sum[u] += Calc(v); } return sum[u]; } inline void Solve() { dfs(1); for (int i = 1; i <= n; ++ i) sdom[i] = i; for (int t = timer; t; -- t) { int u = id[t]; for (int v : vec[u]) { d.pushll(v); if (sdom[d.mn[v]] == u) idom[v] = u; else idom[v] = d.mn[v]; } if (t == 1) continue; for (int i = F.head[u]; i; i = F[i].nex) { int v = F[i].to; if (dfn[v] < dfn[sdom[u]]) sdom[u] = v; else if (dfn[v] > dfn[u]) { d.pushll(v); if (dfn[sdom[d.mn[v]]] < dfn[sdom[u]]) sdom[u] = sdom[d.mn[v]]; } } vec[sdom[u]].push_back(u); d.fa[u] = fa[u]; } for (int t = 2; t <= timer; ++ t) if (idom[id[t]] != sdom[id[t]]) idom[id[t]] = idom[idom[id[t]]]; for (int i = 2; i <= n; ++ i) T.add(idom[i], i); Calc(1); } int main() { scanf ("%d%d", &n, &m); for (int i = 1; i <= m; ++ i) { int u, v; scanf ("%d%d", &u, &v); G.add(u, v); F.add(v, u); } Solve(); for (int i = 1; i <= n; ++ i) printf ("%d ", sum[i]); return puts(""), 0; } ```