支配树

# 支配树
在一个有向图中，有一个起点R，对于任意点W，对于R->W的任意路径都经过点P，则称P为W的支配点。设idom[i]表示距离i最近的支配点。在原图基础上，idom[i]向i连边构成一颗新树，称为支配树
##支配树的性质
1.支配树是以R为根的一棵树
2.对于任意点i，到根r路径上经过的点集{xi}是原图上r->i的必经点
3.对于任意的i，它是子树中每个点的必经点
## 求得
### 半必经点
在dfs搜索树中，对于一个节点Y，存在某个点X能够通过一系列点pi（不包含X和Y）到达点Y且?i dfn[i]>dfn[Y]，我们就称X是Y的半必经点，记做semi[Y]=X
通俗理解：semi[x]就是x在dfs树中所有祖先中z，能不经过 z? 和 x? 之间的树上的点而到达 x? 的点中深度最小的。
###半必经点性质

1. semi[x]一定是x的祖先
2. semi[x]一定是确定的
3. 半必经点不一定是必经点
4. semi[x]深度不小于idom[x]，即idom[x]在semi[x]祖先链上

~~证明的话，咕咕了~~
### 半必经点的作用
保留dfs树的树边，连接semi[i]->i构建新图。不改变原图支配关系，且构成一个dag图。
### 计算
对于点x，有边(y,x)
? 若dfn[y]$<$dfn[x](树边或前向边） 且dfn[y]$<$dfn[semi[x]] ,semi[x]=y
? 根据定义显然
? 若dfn[y]>dfn[x]（后向边或横叉边），找到y的一个祖先semi值最小
的z且dfn[z]>dfn[x]，用semi[z]更新semi[x]
## 计算idom
### 性质

1. idom[x]的深度不大于semi[x]
2. 设点集P是semi[x]（不包含）到x路径上的点，t是P中semi最小的点(1、若semi[t]=semi[x],则idom[x]=semi[x]2、若semi[t]!=semi[x],则idom[x]=idom[t])

## 算法

1. 按dfs序搜索原图得到dfn，从dfn大到小考虑节点
2. 利用带权并查集维护每个点到祖先链上semi值最小值
3. 设当前计算semi[x],对于（y,x）若dfn[y]>dfn[x],则直接根据 更新（y的semi已经计算完）若dfn[y]$<$dfn[x]，则semi[y]没有更新，y是并查集独立点， 同样更新
4. 用x=semi[y]->y更新y的idom，直接查询y祖先链上最小值
5. 最后将semi[x]!=idom[x]的节点idom按dfn从小到大刷新一次

## 代码实现
HDU4694

#include
using namespace std;
const int N=1e5+10;
vector<int>fg[N];vector<int>gg[N];vector<int>ng[N];
int n,m,cnt,tot,rt;
int num[N],val[N],size[N],du1[N],du2[N],fa[N],dfn[N],semi[N],idom[N],fir[N],nxt[N],ver[N],col[N];
void init(){
    cnt=tot=rt=0;
    for(int i=1;i<=n;i++)fg[i].clear(),gg[i].clear(),ng[i].clear();
    memset(val,0,sizeof val);memset(num,0,sizeof num);
    memset(du1,0,sizeof du1);memset(du2,0,sizeof du2);
    memset(fa,0,sizeof fa);memset(dfn,0,sizeof dfn);
    memset(semi,0,sizeof semi);memset(idom,0,sizeof idom);
    memset(fir,0,sizeof fir);memset(nxt,0,sizeof nxt);
    memset(ver,0,sizeof ver);memset(col,0,sizeof col);
}
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
    dfn[x]=++cnt,num[cnt]=x;
    for(int i=fir[x];i;i=nxt[i]){
        int y=ver[i];if(dfn[y]) continue;
        fa[y]=x;dfs(y);
    }
}
int find(int x){
    if(col[x]==x) return x;
    int fx=find(col[x]);
    if(dfn[semi[val[col[x]]]]val[col[x]];
    col[x]=fx;return fx;
}
void tarjan(){
    for(int j=cnt;j>1;j--){
        int x=num[j];
        for(int i=0;i){
            int y=fg[x][i];if(!dfn[y]) continue;
            find(y);
            if(dfn[semi[val[y]]]<dfn[semi[x]])
                semi[x]=semi[val[y]];
        }
        gg[semi[x]].push_back(x);
        col[x]=fa[x];int now=fa[x];
        for(int i=0;i){
            int x=gg[now][i];
            find(x);
            if(semi[val[x]]==now) idom[x]=now;
            else idom[x]=val[x];
        }
    }
    for(int i=2;i<=cnt;i++){
        int x=num[i];
        if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
        ng[idom[x]].push_back(x);
    }
}
void dfsans(int x,int sum){
    du2[x]=x+sum;
    for(int i=0;i)
        dfsans(ng[x][i],sum+x);
}
int main(){
    //freopen("nmmp.cpp","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
    int x,y;init();
    for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),fg[y].push_back(x);
    for(int i=1;i<=n;i++){col[i]=val[i]=semi[i]=i;}
    dfs(n);tarjan();dfsans(n,0);
    for(int i=1;i"%d ",du2[i]);
    printf("%d",du2[n]);puts("");
    }
    return 0;
}

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #pragma GCC optimize(3)
  7 using namespace std;
  8 const int    MAXN = 50000 + 10;
  9 int        n, m;
 10 int read()
 11 {
 12     int        x    = 0, f = 1;
 13     static char    c    = getchar();
 14     while ( c<'0' || c>'9' )
 15     {
 16         if ( c == '-' )
 17             f = -1;
 18         c = getchar();
 19     }
 20     while ( c >= '0' && c <= '9' )
 21     {
 22         x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar();
 23     }
 24     return(x * f);
 25 }
 26 
 27 
 28 struct Graph {
 29     vector<int>    G[MAXN];
 30     void        add( int f, int t )
 31     {
 32         G[f].push_back( t );
 33     }
 34 
 35 
 36     void reset()
 37     {
 38         for ( int i = 1; i <= n; i++ )
 39             G[i].clear();
 40     }
 41 }        G, rG, sG, tree;
 42 int        dfn[MAXN], id[MAXN], dfn_cnt, semi[MAXN], idom[MAXN], dep[MAXN];
 43 int        degree[MAXN];
 44 int        fa[MAXN];
 45 int        lca[MAXN][20];
 46 int        belong[MAXN], mn[MAXN]; /* bcj */
 47 bool        vis[MAXN];
 48 int        q[MAXN], top;
 49 int        sum;
 50 queue<int>    Q;
 51 int        ans[MAXN];
 52 void reset()
 53 {
 54     dfn_cnt = 0; top = 0; sum = 0;
 55     memset( lca, 0, sizeof(lca) );
 56     memset( vis, false, sizeof(vis) );
 57     memset( fa, 0, sizeof(fa) );
 58     memset( degree, 0, sizeof(degree) );
 59     memset( dfn, 0, sizeof(dfn) );
 60     memset( id, 0, sizeof(id) );
 61     memset( semi, 0, sizeof(semi) );
 62     memset( dep, 0, sizeof(dep) );
 63     memset( ans, 0, sizeof(ans) );
 64     memset( mn, 0, sizeof(mn) );
 65     for ( int i = 1; i <= n; i++ )
 66     {
 67         belong[i] = i; mn[i] = i;
 68     }
 69     G.reset(), sG.reset(), tree.reset(), rG.reset();
 70 }
 71 
 72 
 73 void getdfn( int x, int f )
 74 {
 75     dfn[x]    = ++dfn_cnt; id[dfn_cnt] = x;
 76     semi[x] = x; fa[x] = f;
 77     vis[x]    = true;
 78     for ( int i = 0; i < G.G[x].size(); i++ )
 79     {
 80         int t = G.G[x][i];
 81         if ( vis[t] )
 82             continue;
 83         getdfn( t, x );
 84     }
 85 }
 86 
 87 
 88 int find( int x )
 89 {
 90     if ( x == belong[x] )
 91         return(x);
 92     int f = belong[x]; belong[x] = find( f );
 93     if ( dfn[semi[mn[f]]] < dfn[semi[mn[x]]] )
 94         mn[x] = f;
 95     return(fa[x]);
 96 }
 97 
 98 
 99 int LCA( int x, int y )
100 {
101     if ( dep[x] < dep[y] )
102         swap( x, y );
103     int d = dep[x] - dep[y];
104     for ( int i = 18; i >= 0; i-- )
105         if ( d & (1 << i) )
106             x = lca[x][i];
107     for ( int i = 18; i >= 0; i-- )
108     {
109         if ( lca[x][i] ^ lca[y][i] )
110             x = lca[x][i], y = lca[y][i];
111     }
112     return(x == y ? x : lca[x][0]);
113 }
114 
115 
116 void worklca( int x )
117 {
118     int anc = sG.G[x][0];
119     for ( int i = 0; i < sG.G[x].size(); i++ )
120     {
121         anc = LCA( anc, sG.G[x][i] );
122     }
123     dep[x]        = dep[anc] + 1;
124     idom[x]        = anc;
125     lca[x][0]    = anc;
126     for ( int i = 1; i <= 18; i++ )
127         lca[x][i] = lca[lca[x][i - 1]][i - 1];
128 }
129 
130 
131 void lengauer_tarjan()
132 {
133     getdfn( n, 0 );
134     dfn[0] = 0x3f3f3f3f;
135     for ( int w = dfn_cnt; w > 1; w-- )
136     {
137         int x = id[w];
138         for ( int i = 0; i < rG.G[x].size(); i++ )
139         {
140             int t = rG.G[x][i];
141             if ( !dfn[t] )
142                 continue;
143             find( t );
144             if ( dfn[semi[mn[t]]] < dfn[semi[x]] )
145                 semi[x] = semi[mn[t]];
146         }
147         sG.add( semi[x], x );
148         belong[x] = fa[x];
149         int now = fa[x];
150         for ( int i = 0; i < sG.G[now].size(); i++ )
151         {
152             int x = sG.G[now][i];
153             find( x );
154             if ( semi[mn[x]] == now )
155                 idom[x] = now;
156             else idom[x] = mn[x];
157         }
158     }
159     for ( int i = 2; i <= dfn_cnt; i++ )
160     {
161         int x = id[i];
162         if ( idom[x] != semi[x] )
163             idom[x] = idom[idom[x]];
164         tree.add( x, idom[x] );
165     }
166 }
167 
168 
169 int getans( int x )
170 {
171     int ans = x;
172     for ( int i = 0; i < tree.G[x].size(); i++ )
173     {
174         ans += getans( tree.G[x][i] );
175     }
176     return(ans);
177 }
178 
179 
180 int main()
181 {
182     while ( scanf( "%d%d", &n, &m ) != EOF )
183     {
184         int f, t;
185         reset();
186         for ( int i = 1; i <= m; i++ )
187         {
188             f = read(), t = read();
189             G.add( f, t ); rG.add( t, f );
190         }
191         lengauer_tarjan();
192         for ( int i = 1; i <= n; i++ )
193             printf( "%d ", getans( i ) );
194         puts( "" );
195     }
196 }