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

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

摘抄自 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]<<" ";
}