1. 定义

1.1 DAG上的支配树

作用：给定一个$DAG$，询问从起点到终点必经的点，即去掉这个点以及与这个点相连的边，无法到达终点(无向图概念中的割点)，可以建立支配树来求解

结构：树形结构，将图的起点作为根节点，每个节点都是到达根节点的必经点。

建图：

• 点$u$的在支配树上的父亲是所有能走到点$u$在支配树上的$LCA$，于是可以通过$O(nlogn)$复杂度通过倍增实现。
• 具体来说，通过拓扑排序得到拓扑序，对于每个点根据反向边的$LCA$得到该点的父亲，从而建立$DAG$上的支配树

2. 例题

2.1 BZOJ-2815-[ZJOI2012]灾难

模板题

#include <bits/stdc++.h>

using namespace std;

#define N 1000010
#define DEG 20

struct Graph {
    struct Edge {
        int to, nxt;

        Edge() {}
    
        Edge(int _to, int _nxt) {
            to = _to;
            nxt = _nxt;
        }
    } edge[N];
    
    int head[N], tot;
    
    void Init() {
        memset(head, -1, sizeof head);
        tot = 0;
    }
    
    void addedge(int u, int v) {
        edge[tot] = Edge(v, head[u]);
        head[u] = tot++;
    }
} G[2], zp;

int n;
int fa[N][DEG], dep[N], du[N], sze[N];

struct Tree {
    int LCA(int u, int v) {
        if (u == -1) {
            return v;
        }
        if (v == -1) {
            return u;
        }
        if (dep[u] > dep[v]) {
            swap(u, v);
        }
        for (int det = dep[v] - dep[u], i = 0; det; det >>= 1, ++i) {
            if (det & 1) {
                v = fa[v][i];
            }
        }
        if (u == v) return u;
        for (int i = DEG - 1; i >= 0; --i) {
            if (fa[u][i] == fa[v][i]) {
                continue;
            }
            u = fa[u][i];
            v = fa[v][i];
        }
        return fa[u][0];
    }

    void DFS(int u) {
        sze[u] = 1;
        for (int i = zp.head[u]; ~i; i = zp.edge[i].nxt) {
            int v = zp.edge[i].to;
            if (sze[v] == 0) {
                DFS(v);
            }
            sze[u] += sze[v];
        }
    }
    
    void solve() {
        queue<int> que;
        vector<int> Q;
        for (int i = 1; i <= n; ++i) {
            if (du[i] == 0) {
                que.push(i);
            }
        }
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            Q.push_back(u);
            for (int i = G[0].head[u]; ~i; i = G[0].edge[i].nxt) {
                int v = G[0].edge[i].to;
                --du[v];
                if (du[v] == 0) {
                    que.push(v);
                }
            }
        }
        for (int i = 0, len = Q.size(); i < len; ++i) {
            int u = Q[i];
            int root = -1;
            for (int j = G[1].head[u]; ~j; j = G[1].edge[j].nxt) {
                int v = G[1].edge[j].to;
                root = LCA(root, v);
            }
            if (root == -1) {
                root = 0;
            }
            zp.addedge(root, u);
            fa[u][0] = root;
            dep[u] = dep[root] + 1;
            for (int j = 1; j < DEG; ++j) {
                if (fa[u][j - 1]) {
                    fa[u][j] = fa[fa[u][j - 1]][j - 1];
                }
            }
        }
        DFS(0);
    }
} tree;

int main() {
    scanf("%d", &n);
    G[0].Init(), G[1].Init(), zp.Init();
    for (int i = 1, x; i <= n; ++i) {
        while (~scanf("%d", &x) && x) {
            G[0].addedge(x, i);
            G[1].addedge(i, x);
            du[i]++;
        }
    }
    tree.solve();
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", sze[i] - 1);
    }
    return 0;
}