【学习笔记】支配树基础理论

本来没想着写这么多的，结果写着写着就发现引理搞的有点多了，感觉有点冗余。

摘抄自 oi-wiki 。

Part 1

考虑在任意 有向图 上钦定一个入口节点$s$，对于一个节点$u$，若从$s$到$u$的每一条路径都经过某一个节点$v$，那么称$v$支配$u$，记作$v\operatorname{dom}u$。

对于从$s$出发无法到达的结点，讨论其支配关系是没有意义的，因此假设$s$能到达图上任何一个节点。

引理1：$s$是所有节点的支配点；任意一个节点都是其自身的支配点

引理2：仅考虑简单路径得出的支配关系与所有路径得出的关系相同

引理3：如果$u\operatorname{dom}v$，$v\operatorname{dom}w$，则$u\operatorname{dom}w$

引理4：如果$u\operatorname{dom}v，v\operatorname{dom}u$，则$u=v$

引理5：若$u\ne v\ne w$，$u\operatorname{dom}w$且$v\operatorname{dom}w$，则有$u\operatorname{dom}v$或$v\operatorname{dom}u$

证明：考虑一条$s\to u\to v\to w$的路径，若$u$不支配$v$，则存在一条$s\to v\to w$的路径，与$u\operatorname{dom}w$矛盾（注意我们只考虑简单路径的情况）

将任意节点$u$的支配点中，除自身外与自己距离最近的节点$v$称作$u$的直接支配点，记作$\operatorname{idom}(u)=v$。

比较直观的理解：设$u$的支配点集为$\{s_1,s_2,...,s_k\}$，则一定存在一条路径$s\to s_1\to s_2\to ...\to s_k\to u$，显然$s_k$就是$u$的直接支配点。

将除$s$外每一个节点$u$从$\operatorname{idom}(u)$向$u$连边，我们就得到了一颗支配树。

结论：对于一个节点$u$的支配点集$S$，若$v\in S$满足$\forall w\in S\ \backslash \ \{u,v\},w\operatorname{dom}v$，则$\operatorname{idom}(u)=v$（结合前面的理解不难证明，这个可能构造题会用到）

Part 2

对于$DAG$，我们可以直接根据拓扑序求解。

引理6：在有向图上，$v\operatorname{dom}u$当且仅当$\forall w\in pre(u),v\operatorname{dom} w$

因此，$u$的支配点一定是其所有前驱节点在支配树上的公共祖先。使用$LCA$算法即可解决。

Part 3

求解任意有向图中支配树的方法：

约定这里$w\to v$指的是存在 DFS 树上从$w$到$v$的路径。注意这个表述并不严谨，更严谨的记号可以参考 这篇博客。后文一些引理的证明也 参考了这篇博客 。

首先从$s$出发对有向图进行 DFS ，所经过的点和边形成了一棵树$T$。令$dfn(u)$表示节点$u$第几个被遍历到；定义 $u\lt v$ 当且仅当 $dfn(u)\lt dfn(v)$。

引理7（路径引理）：如果两个点$v,w$满足$v\le w$，那么任意$v$到$w$的路径经过$v,w$的公共祖先（不一定是$LCA$）

证明主要是利用横叉边一定是从大的点到小的点。

定义节点$u$的半支配点为，从这个节点$v$出发存在一条路径，路径上除了$u,v$之外的每个节点都大于$u$的结点中最小的那一个，记作$\operatorname{sdom}(u)$。

引理8：对于任意节点$u$，$\text{sdom(u)} \lt u$。

显然$fa(u)\lt u$，并且是合法的半支配点。

引理9：对于任意节点$u$，$\text{idom(u)}$是其在$T$上的祖先

引理10：对于任意节点$u$，$\text{sdom}(u)$是其在$T$上的祖先

如果$v$不是$u$的祖先，并且$v\lt u$，那么$v$到$u$的路径一定经过$u,v$的公共祖先（路径引理），不满足$v$是支配点的条件。

引理11：对于任意节点$u$，$\text{idom}(u)$是$\text{sdom}(u)$的祖先

引理12：对于任意节点$u\ne v$满足$v$是$u$的祖先，则要么有$v$是$\text{idom(u)}$的祖先，要么$\text{idom(u)}$是$\text{idom}(v)$的祖先

证明：对于任意在$v$和$\text{idom}(v)$之间的节点$w$，一定存在一条不经过$w$的，从$s$到$\text{idom}(v)$再到$v$的路径。因此这些节点一定不是$\text{idom(u)}$，因此$\text{idom(u)}$要么是$v$的后代，要么是$\text{idom(v)}$的祖先

引理13：
$$ \text{sdom}(u)=\min(v|(v,u)\in E,v\lt w\cup \text{sdom}(w)|w>u,\exists (v,u)\in E,w\to v) $$

可以从大到小枚举点，用带权并查集维护，从而求得所有点的半支配点。

引理14：对于任意$u\ne r$，如果所有$\text{sdom(u)}$和$u$之间（不包括$\text{sdom(u)}$）的点$v$满足$\text{sdom(v)}\ge \text{sdom(u)}$，那么$\text{idom(u)}=\text{sdom(u)}$

证明：只需证明$\text{sdom(u)}$支配$u$即可。考虑任意$s$到$w$的路径，取上面最后一个编号小于$\text{sdom(u)}$的$x$，则一定存在$y$满足$y$在$\text{sdom(u)}$和$u$之间。同理，考虑取最小的的$y$，如果$y$不是$\text{sdom(u)}$，那么根据条件，$\text{sdom(y)}\ge \text{sdom(u)}$，所以$x$不可能是$\text{sdom(y)}$，因此从$x$到$y$的路径上也存在一个$\text{sdom(y)}$和$y$之间的节点$w$（这与之前的推理是一样的），这与$y$最小矛盾。

这个结论比较重要，能让我们比较直观的感受到半支配点的作用。

引理15：对于任意$u$，令$v$为$\text{sdom(u)}$和$u$之间（不包括$\text{sdom(u)}$）$\text{sdom(v)}$最小的一个，并且$\text{sdom(v)}\le \text{sdom(u)}$，那么$\text{idom(u)}=\text{idom(v)}$

证明：条件可以写成$\text{sdom(v)}\to \text{sdom(u)}\to v\to u$。

由引理12可知 $\text{idom(u)}\to \text{idom(v)}$ 或 $v\to \text{idom(u)}$，排除后面那种（引理11），只需证明$\text{idom(v)}$支配$u$。这是比较显然的。

引理16：对于任意$u$，令$v$为$\text{sdom}(u)$和$u$之间（不包括$\text{sdom(u)}$）$\text{sdom}(v)$最小的一个，则：

$$ \text{idom(u)}= \begin{cases} \text{sdom(u)}& \text{sdom(v)}=\text{sdom(u)} \\ \text{idom(v)}&\text{sdom(v)}\lt \text{sdom(u)} \end{cases} $$

说白了就是前两个引理。

可以发现求$v$的过程和求半支配点是类似的，因此当从大到小处理到$\text{sdom(u)}$的时候就可以顺便求出$u$对应的信息。最后再从小到大遍历一遍即可。

复杂度$O(n+m)$。

吐槽：oi-wiki上的写法是错的，会被叉。网上的代码就没几个靠谱的。。。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
int n,m,mn[N],dfn[N],num,ps[N],idm[N],sdm[N],fa[N],fth[N],sz[N];
vector<int>G[N],G2[N],G3[N],G4[N];
void dfs(int u){
    dfn[u]=++num,ps[num]=u;
    for(auto v:G[u]){
        if(!dfn[v])fth[v]=u,dfs(v);
    }
}
int find(int x){
    if(fa[x]==x)return x;
    int tmp=fa[x];
    fa[x]=find(fa[x]);
    if(dfn[sdm[mn[tmp]]]<dfn[sdm[mn[x]]]){
        mn[x]=mn[tmp];
    }return fa[x];
}
void solve(){
    dfs(1);
    for(int i=1;i<=n;i++)fa[i]=sdm[i]=mn[i]=i,idm[i]=1;
    for(int i=num;i>=2;i--){
        int u=ps[i],res=inf;
        for(auto v:G2[u]){
            if(dfn[v]<dfn[u]){
                res=min(res,dfn[v]);
            }
            else{
                find(v);
                res=min(res,dfn[sdm[mn[v]]]);
            }
        }
        //u=fth[u];
        for(auto v:G3[u]){
            find(v);
            if(sdm[mn[v]]==sdm[v]){
                idm[v]=u;
            }
            else{
                idm[v]=mn[v];
            }
        }
        sdm[u]=ps[res];
        G3[sdm[u]].pb(u);
        fa[u]=fth[u];
    }
    for(int i=2;i<=num;i++){
        int u=ps[i];
        if(idm[u]!=sdm[u]){
            idm[u]=idm[idm[u]];
        }
    }
}
void build(){
    for(int i=2;i<=n;i++)G4[idm[i]].pb(i);
}
void dfs2(int u){
    sz[u]=1;
    for(auto v:G4[u])dfs2(v),sz[u]+=sz[v];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y),G2[y].pb(x);
    }
    solve();
    build();
    dfs2(1);
    for(int i=1;i<=n;i++)cout<<sz[i]<<" ";
}