跳转至

支配树

支配

想要了解支配树，我们需要先知道什么是支配：

支配的定义

对于一个点 \(x\) ，如果 \(s\) 到 \(x\) 的所有路径都需要经过 \(y\) 。

那么称 \(y\) 支配 \(x\) （在 \(s\) 下）。一般使用数学符号表示为 \(y~dom~x\) 。

对于支配有一些优秀的性质：

传递性： 对于 \(x~dom~y\) 且 \(y~dom~z\) 那么满足 \(x~dom~z\)。

自反性： 对于一个节点 \(x\) ，一定满足 \(s~dom~x\) 且 \(x~dom~x\)。

编不出名字的性质： 如果存在 \(a~dom~x\) 且 \(b~dom~x\) 那么一定满足 \(a~dom~b\) 或 \(b~dom~a\) 。

（上述性质都是可以通过定义简单证明的，这里就不多多赘述）

支配树

定义

支配树是通过支配关系进行构建的，其满足：

给定有向图 \(G\) 和根 \(r\)，支配树满足 \(x\) 的子树恰好是那些删去 \(x\) 后 \(r\) 不可达的点。

此时可以发现对于一个节点 \(x\) 的连边就是 \(idom(x)\) 即所有能够支配他的节点中理他最近的一个。

构建方法

这里分两种情况： DAG 和 非DAG。

对于 DAG 的情况，相对来说比较好构建。

DAG 的情况

我们发现此时对于一个 DAG ，当 \(x~dom~y\) ,此时一定满足 \(x\) 的拓扑序在 \(y\) 之前。

所以我们先求出 拓扑序 ，然后从前往后扫描，然后计算在拓扑树上的父亲节点在当前支配树的 LCA ，然后连接这个节点和当前节点。

这是因为我们要求对于节点 \(x\) ，他的所有父亲链上的节点应道是所有支配他的节点。 而到达 \(x\) 的路径一定会经过 \(x\) 在原树上的一个父亲。

然后如果要把每一条经过每一个父亲的道路同时切断。 相当于就是其所有父亲在支配树上的祖先链的交集。 因为同时要求离 \(x\) 距离最近，所以自然就是其所有父亲的 LCA。

自然实现十分简单：

DAG 参考代码 
 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
struct domTree{
    vector<int> v[N],g[N];

    int du[N];
    void add(int x,int y) {
        v[x].push_back(y);
        du[y]++;
    }

    int p[N];

    int fa[N][20], dep[N];
    int lca(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=19; i>=0; i--)
            if(dep[fa[x][i]] >= dep[y])
                x=fa[x][i];
        if(x==y) return x;
        for(int i=19; i>=0; i--)
            if(fa[x][i] != fa[y][i])
                x=fa[x][i], y=fa[y][i];
        return fa[x][0];
    }

    void Topo() {
        queue<int> q;
        for(int i=1; i<=n; i++) {
            if(du[i]==0) q.push(i), p[i]=0;
            else p[i]=-1;
        }

        while(!q.empty()) {
            int x=q.front(); q.pop();
            g[p[x]].push_back(x);

            dep[x]=dep[p[x]]+1;
            fa[x][0]=p[x];
            for(int i=1; i<=19; i++) {
                fa[x][i]=fa[fa[x][i-1]][i-1];
            }

            for(auto y: v[x]) {
                if(p[y]==-1) p[y]=x;
                else p[y]=lca(p[y],x);

                if((--du[y]) == 0) q.push(y);
            }
        }
    }

    int siz[N];
    void Getsiz(int x) {
        siz[x]=1;
        for(auto y: g[x]){
            Getsiz(y);
            siz[x]+=siz[y];
        }
    }

    void main() {
        Topo();
        Getsiz(0);
    }

    void clear(){
        for(int i=1; i<=n; i++) {
            v[i].clear(), g[i].clear();
            du[i]=p[i]=dep[i]=siz[i]=0;
        }
    }
};
domTree dom;

对于非支配树的情况，就会比较麻烦。

这种情况，对于一般的题目只需要写一个 \(\mathcal O(nm)\) 的暴力就可以了，具体做法就是先根据定义的之每一个顶点支配哪一些点，从而得知每一个点的子树 \(siz\) 大小, 然后每一个节点 \(x\) 的 \(fa_x\) 应当为满足 \(y~dom~x\) 时 \(siz_y\) 最小的一个。

普通树——示例代码 
 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
struct domTree{
    vector<int> v[N],g[N];

    void add(int x,int y) {
        v[x].push_back(y);
    }

    bitset<N> vis;
    void bfs(int del) {
        queue<int> q;
        vis.reset();
        q.push(1);

        while(!q.empty()) {
            int x=q.front(); q.pop();
            if(x==del) continue;
            vis[x]=1;

            for(auto y: v[x]){
                if(vis[y] || y==del) continue;
                vis[y]=1;
                q.push(y);
            }
        }
    }

    int cnt,dfn[N];
    void Getdfn(int x){
        dfn[x]=++cnt;
        for(auto y: g[x]) {
            if(!dfn[y]) Getdfn(y);
        }
    }

    int fa[N];
    int siz[N];
    void main() {
        for(int i=1; i<=n; i++) fa[i]=0, siz[i]=0;
        for(int i=1; i<=n; i++) {
            bfs(i);

            for(int j=1; j<=n; j++) {
                if(vis[j]==0) siz[i]++;
            }

            for(int j=1; j<=n; j++)
                if(vis[j]==0 && j!=i) {
                    if(fa[j]==0 || siz[i]<siz[fa[j]])
                        fa[j]=i;
                }
        }
        for(int i=1; i<=n; i++) g[fa[i]].push_back(i);

        Getdfn(1);
    }

};
domTree dom;

应用

直接看例题：

P7520 [省选联考 2021 A 卷] 支配

首先肯定是要先建出来一颗支配树的， 然后考虑加上一条边 \((u,v)\) 之后的变化。

有一个十分明显的结论： 增加边之后支配集合一定只会变少。

如果对于一个节点 \(x\) 他的支配集合有变化， 那么一定存在一条道路 \(1 \to u \to v \to x\) 。并且这条道路不会经过支配树上 \(1 \to x\) 中的某一个点。

但是很明显如果想要处理不经过任意一个点不太好求，但是我们发现如果节点 \(x\) 支配改变了，那么他在支配树上的子树也一定改变了。 所以我们更改条件为仅仅不经过 \(idom(x)\) 即 \(x\) 在支配树上的父亲。

此时求解的东西就变成了需要寻找 \(1 \to u \to v \to x\) 的路径并且不经过一个节点 \(fa_x\) ，通过图像如下：

图炸了

然后我们只需要对于每一个节点 \(x\) 预处理，删去 \(fa_x\) 之后跑返图看一下能够从拿一些节点通过不走 \(fa_x\) 到 \(x\) 。

当然还有一点是 \(fa_x\) 不能为 \(1 \to u\) 的支配点，否则此时 \(fa_x\) 在 \(u\) 上方并且是必经点。