支配树

支配树学习笔记

定义：

• 表示 的DFS序。
• 对于DFS树上的两个点 ，定义 当且仅当 的DFS序比 的DFS序小

问题

给定一张有向图 和源点 ，并且 可达所有点。称点 支配点 当且仅当所有从 到 的路径必定经过点 （特别地，一个点不支配它自身），支配树就是用来刻画这样的支配关系的结构。

支配关系的性质

若 支配点 ，则称 是 的支配点，记作 。一个关键性质是：支配关系构成偏序。

易证如下性质：

• 若 且 ，则
• 不支配它自身（特别定义）
• 若 并且 ，那么必然有 或

依据如上三条性质，定义 的最近支配点为离它最近的支配点，它被 的其它所有支配点支配，记作 。

换句话说，存在一个根为 的树形结构，点 的所有祖先即为 的支配点， 的父亲为 的最近支配点，称该结构为支配树，下面我们考虑如何得到该结构。

支配树的求解

下面，我们首先探讨 为DAG时如何求出其支配树，然后再考虑如何将一般图的支配树等价到一个DAG上的支配树，套用求DAG支配树的解法即可。

DAG的支配树

当 为一个DAG时，点 的最近支配点就是它的所有前驱在支配树上的LCA，于是我们只需要按照拓扑序，实现动态加叶子以及快速求LCA即可，这可以用倍增LCA解决，总时间复杂度为 。

一般图的支配树

我们分两步解决这个问题，第一步是将其规约到DAG的支配树，第二步是快速求出归约到的那个DAG。

将一般图的支配树转化为DAG的支配树

首先以 为根构建出任意一棵DFS树，称为树 ，显然， 的支配点在DFS树上必然是 的祖先（反过来则不一定成立）。

如果 不支配 （其中 是 在树 上的祖先），那么必然存在一个子树 之外的结点 ，它能不经过点 到达点 （从 到达 是不会经过点 的，因为它不在 的子树内）。

如何不经过 到达 ？必然是先到达了树 上 路径上的某一点 （），然后通过树边向下到达 。记DFS树上 与 的LCA为 ，则树上路径 （不含端点）中的所有点均不再支配 的子树，显然，对于某一个固定的 ，只有最远的 是有用的，称该点为 的半支配点，记作 。

换句话说， 是 的半支配点，当且仅当：

• 是 在DFS树上的祖先
• 可以从 出发，不经过树上路径 （不含端点）外的其它点到达
• 是满足上述条件且深度最浅的那个点

我们在DFS树中加入边 ，相当于消除了 （不含端点）上的点对 子树的支配，如果在DFS树中对所有的 都加入边 （其中 是 的半支配点），那么该图的支配关系与原图完全相同！

于是我们得到了最为关键的一条引理，叙述如下。

引理： 原图 的支配树等价于仅考虑如下边的图的支配树

• DFS树上的树边
• 每个点 的半支配点到 的连边，即对于每个点 ，加入一条边

原因在于图 的每对不支配关系都被第二类边表达了。

注意到我们构造出的新图是一个DAG（ 是 的祖先），而求解DAG的支配树是我们最开始就解决了的问题，所以我们的任务仅有：如何对每个点 求出其半支配点.

半支配点的求解

首先，我们给出一个性质：路径 上，除端点以外的点的DFS序均大于 ，证明如下：

首先，路径中到达的深度最小的结点即为 ，否则设深度最小的结点为 ，那么 满足半支配点的前两个条件且深度更小，那么 才应该是 的半支配点。

将从 到达 的路径分为两部分，

1. 从 到达 的子树
2. 从 的子树到达

对于第一部分，必然是先走到一个异于 所在子树的子树，再通过横叉边到达 的子树，而走横叉边会使DFS序减小，并且原先子树中每个点的DFS序都要大于终点的DFS序，所以第一部分中的点满足条件。

对于第二部分， 子树中的点的DFS序显然都大于 的DFS序，结论自然成立。

因此， 即为，除端点外只经过DFS序大于 的点可以到达 的点中DFS序最小的那一个。

补充 先前只证明了充分性，但必要性是显然的，即「若一个点 可以只经过DFS序大于 的点到达 ，那么 半支配 」，其中 是 的祖先。

引理：

按照DFS序的逆序，用并查集维护DFS树上当前的连通块即可求出每个点的半支配点。

于是我们就成功在 的时间复杂度内构造出了这个DAG，套用DAG上做法即可。

转DAG后在DAG上求解支配树

// 洛谷 P5180
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10, M = 1e6 + 10;
int n, m, h[N], e[M], ne[M], idx;
vector<int> pre[N], son[N]; int fa[N];
inline void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfn[N], A[N], dfs_clock;
int sdom[N];
void dfs(int u) {
    dfn[u] = ++dfs_clock, A[dfs_clock] = u;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(!dfn[v]) son[u].emplace_back(v), fa[v] = u, dfs(v);
    }
}
int p[N], ans[N];
int find(int x) {
    if(x == p[x]) return x;
    find(p[x]);
    if(dfn[ans[p[x]]] < dfn[ans[x]]) ans[x] = ans[p[x]];
    p[x] = p[p[x]]; return p[x];
}

int anc[20][N], dep[N];
inline int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i --)
        if(dep[anc[i][u]] >= dep[v]) 
            u = anc[i][u];
    if(u == v) return u;
    for(int i = 19; i >= 0; i --)
        if(anc[i][u] != anc[i][v])
            u = anc[i][u], v = anc[i][v];
    return anc[0][u];
}

int siz[N]; vector<int> DT_son[N];
void dfs_DT(int u) {
    siz[u] = 1;
    for(int v : DT_son[u])
        dfs_DT(v), siz[u] += siz[v];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(h, -1, sizeof h);

    cin >> n >> m;
    for(int i = 0; i < m; i ++) {
        int a, b; cin >> a >> b;
        add(a, b); pre[b].emplace_back(a);
    }
    dfs(1); assert(dfs_clock == n);
    for(int i = 1; i <= n; i ++)
        p[i] = i;
    for(int i = n; i >= 2; i --) {
        int u = A[i]; sdom[u] = u;
        for(int v : pre[u]) {
            if(dfn[v] >= dfn[u]) {
                find(v);
                if(dfn[ans[v]] < dfn[sdom[u]])
                    sdom[u] = ans[v];
            } else if(dfn[v] < dfn[sdom[u]]) sdom[u] = v; 
        }
        ans[u] = sdom[u];
        for(int v : son[u]) p[v] = u;
    }
    sdom[1] = 1, dep[1] = 1;
    for(int i = 2; i <= n; i ++) {
        int u = A[i];
        anc[0][u] = lca(fa[u], sdom[u]); dep[u] = dep[anc[0][u]] + 1;
        DT_son[anc[0][u]].emplace_back(u);
        for(int j = 1; anc[j - 1][u] && (1 << j) <= n; j ++)
            anc[j][u] = anc[j - 1][anc[j - 1][u]];
    }
    dfs_DT(1);
    for(int i = 1; i <= n; i ++)
        cout << siz[i] << " \n"[i == n];

    return 0;
}

通过半支配点直接求出支配点

上面的方法需要建出很多图，是否可以利用半支配点直接求出支配点呢？

引理 记 是在DFS树中 链上半支配点的DFS序最小的点，那么