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

引理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<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)$最小的一个，则：

idom(u) = { sdom(u) sdom(v) = sdom(u) idom(v) sdom(v) < sdom(u) \text{idom(u)}=

说白了就是前两个引理。

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

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

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

#include
#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]<<" ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79