题解：P5180 【模板】支配树

ERoRaIn · 2024-03-22 22:54:29 · 题解

支配树

作者写这篇文章的原因主要是现有题解要么就毫无证明，要么证明过程不太直观、概念不太清晰，在我的学习过程中困扰了我很久。

我是农历年前学的，由于实力比较弱，那时候经常坐在房间椅子上一个下午想这个算法，勉强看懂证明后草草放弃。这几天回想到这个算法，仔细思考想清楚了之后决定写下本文，方便给像我这样的学习者一个向导。

言归正传，由于作者我之前主要是根据这篇巨佬的文章学习的，因此在表示和论述方法上会有相似，但是证明过程和内容编排多数为自己的想法，使用了更感性的证明论述方法。如果您学术目的比较强，也可以去参考那篇文章。

注例

这里给出了一些本文符号代表的含义，读者不理解时可以来这里检索。

在本文中，使用 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 ，所以可以证明所形成的必为一棵树。
对于点 $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 （左闭右开）链上的点。

证明：
2. 把 T 分为 3 部分， [S,sdom(u)) ， [sdom(u), u) ，[u, n] ，命名为第一、二、三部分；

求解 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 过程，即枚举临点转移的过程。

对于前半部分，由于 sdom(u)\overset{S}{\rightsquigarrow}u 只能经过比 u 大的点，链的起始点只能到 v 为止了。
对于后半部分，即枚举最后一条链的长度，即枚举上一条链是跳到最后一条链的哪一个点的。

其中，后面一种情况的枚举过程可以使用并查集优化，具体见下文代码实现。

求解 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} 。

此时 $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 最小的点，分类讨论：

若 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 不存在。
若 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} 。

可以使用并查集优化。

代码实现

可以参考代码理解。

#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;
}