被树支配的恐惧

前言

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

支配树解决的是一个很现实的问题:假设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;
}
comments powered by Disqus