被树支配的恐惧

Lucas

Jul 31, 2019 • 4 min read

前言

你敢信你有生之年还会被树支配上几次？反正我是被支配了……

支配树解决的是一个很现实的问题：假设S给T通过各种途径提供生(mo)命(fa)之源，但这些途径都有一个共性（都经过一个点），现在你想用最小的代价（摧毁尽可能少的点）抹除T，那么你应该摧毁哪些点

概念

给定一个有向图，给定起点S，终点T，在所有从S到T的路径中，如果删去某个点，则不存在一条路径能够使S到达T，则这个点被称为支配点。由支配点构成的树叫做支配树。支配树是一颗由起点S为根的树，根到树上任意一点路径经过的点都是它的支配点。

主要变量

dfn[x],表示dfs序

id[x], 表示dfs序对应的点

dfa[x], 第一遍dfs中，每个点的父节点

sdom[x], x的半支配点

idom[x], x的支配点

fa[x], 并查集（都懂）

mindfn[x]，从x到其已经被搜过的祖先的dfn的最小值

半支配点的定义（tarjan tql)

性质（证明略）

1：半支配点是唯一的（但是支配点可以有多个）

2:对于任意点w，它的半支配点必定是它在dfs\ tree上的祖先

3：对于任意节点w != s, w的支配点必然是该节点的半支配点的祖先节点

4：假设存在v,w且v是w的祖先，那么idom[w]要么是v的后代，要么是idom[v]的祖先。

求sdom的方法（伪代码）

for_each k in G with cond (dfn[k]>dfn[u] && k.canreach(u))
if(dfn[u]>dfn[v]) 
    sdom[u]=mindfn(v);
else 
    sdom[u]=mindfn{sdom[k]}

求idom的方法

如果图中存在节点v,w,且v支配w，并且w的其他支配点均支配v，我们就称v是w的最近支配点，记作idom[w]=v

（仍然是伪代码）

def P = {all vertex U on route x->sdom[x]}
for_each k=min(dfn[P[i]])
if(sdom[k]==sdom[x])
    idom[x]=sdom[x]
else 
    idom[x]=idom[z]

总体步骤

1：对这张图进行一遍dfs,求出dfn

2：根据dfn大小从大到小遍历求出sdom

3：保留dfs树上的节点和边，求出该点祖先链中sdom的最小值mindfn[v]，然后这个点会成为一颗子树的根，通过带权并查集维护各个子树并连接。通过sdom求出idom

模板

https://www.luogu.org/problem/P5180

给定一张有向图，求从1号点出发，每个点能支配的点的个数

#include <bits/stdc++.h>

using namespace std;

static constexpr int maxn = 300050;

struct node {
    vector<int> e[maxn];
    inline void add(int u, int v) { e[u].push_back(v); }
} a, b, c, d;

int dfn[maxn], id[maxn], dfa[maxn], sdom[maxn], idom[maxn], fa[maxn],
    mindfn[maxn], cnt;

void dfs(int u) {
    dfn[u] = ++cnt;
    id[cnt] = u;
    for (int i : a.e[u]) {
        if (dfn[i]) {
            continue;
        }
        dfa[i] = u;
        dfs(i);
    }
}

int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    int tmp = find(fa[x]);
    if (dfn[sdom[mindfn[fa[x]]]] < dfn[sdom[mindfn[x]]]) {
        mindfn[x] = mindfn[fa[x]];
    }
    return fa[x] = tmp;
}

void zp() {
    for (int i = cnt; i > 1; i--) {
        int u = id[i];
        for (int v : b.e[u]) {
            if (!dfn[v]) {
                continue;
            }
            find(v);
            if (dfn[sdom[mindfn[v]]] < dfn[sdom[u]]) {
                sdom[u] = sdom[mindfn[v]];
            }
        }
        c.add(sdom[u], u);
        fa[u] = dfa[u];
        u = fa[u];
        for (int v : c.e[u]) {
            find(v);
            sdom[mindfn[v]] == u ? idom[v] = u : idom[v] = mindfn[v];
        }
    }
    for (int i = 2; i <= cnt; i++) {
        int u = id[i];
        if (idom[u] != sdom[u]) {
            idom[u] = idom[idom[u]];
        }
    }
}

void zp_write(int n) {
    for (int i = 2; i <= n; i++) {
        d.add(idom[i], i);
    }
}

int ans[maxn];

void dfs2(int u) {
    ans[u] = 1;
    for (int i : d.e[u]) {
        dfs2(i);
        ans[u] += ans[i];
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        a.add(u, v);
        b.add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        sdom[i] = fa[i] = mindfn[i] = i;
    }
    dfs(1);
    zp();
    zp_write(n);
    dfs2(1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

前言

概念