BZOJ2815【ZJOI2012】灾难 <灭绝树+DP>

Posted on Symbols count in article: 637 Reading time ≈ 2 mins.

Problem

标签：灭绝树 DP

Solution

对于一个DAG\mathrm{DAG}，存在一棵树使得这棵树上任意结点若被删除，则在原图上其所有子结点对应的结点都无法被到达。这棵树称为灭绝树。显然，如果构造出这棵灭绝树，则每个结点的灾难值等于其在灭绝树上的子树大小减一。

构建灭绝树需要用增量构造法。首先对原图进行拓扑排序，按拓扑序依次加入每个点。这样可以控制这个点的所有点都会在其加入之前被加入到灭绝树中。假想一个根，向所有入度为00的点连边。对于新加入的点，其被所有先前控制这个点的点的LCA\mathrm{LCA}所控制，即找到其所有“食物”的LCA\mathrm{LCA}，从LCA\mathrm{LCA}向这个点连边即可。这里需要支持动态加点求倍增数组和询问LCA\mathrm{LCA}。构造总复杂度为O(mlog⁡n)O(m\log{n})（mm为原图总边数）。

建出灭绝树后，树形DP\mathrm{DP}一遍，求出每个点的子树大小，即可求得其灾难值。

Code

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
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, sz[MAX_N+5]; vector <int> seq;
int deg[MAX_N+5], dep[MAX_N+5], fa[MAX_N+5][18];
vector <int> G[MAX_N+5], E[MAX_N+5], T[MAX_N+5];
void topo() {
    queue <int> que;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) que.push(i);
    while (!que.empty()) {
        int u = que.front(); seq.push_back(u), que.pop();
        for (int i = 0, v; i < (int)G[u].size(); i++)
            if (!--deg[v = G[u][i]]) que.push(v);
    }
}
void addedge(int f, int u) {
    T[f].push_back(u);
    fa[u][0] = f, dep[u] = dep[f]+1;
    for (int i = 1; i <= 16; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
}
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 16; ~i; i--)
        if (dep[u]-dep[v] >= (1<<i)) u = fa[u][i];
    if (u == v) return u;
    for (int i = 16; ~i; i--)
        if (fa[u][i] ^ fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
void DFS(int u) {
    sz[u] = 1;
    for (int i = 0, v; i < (int)T[u].size(); i++)
        DFS(v = T[u][i]), sz[u] += sz[v];
}
int main() {
    read(n);
    for (int i = 1, x; i <= n; i++) {
        for (read(x); ; read(x)) {
            if (!x) break;
            G[x].push_back(i);
            E[i].push_back(x);
            deg[i]++;
        }
    }
    topo();
    for (int i = 0; i < (int)seq.size(); i++) {
        int u = seq[i];
        if (!E[u].size()) addedge(0, u);
        else {
            int lca = E[u][0];
            for (int i = 1; i < (int)E[u].size(); i++)
                lca = LCA(lca, E[u][i]);
            addedge(lca, u);
        }
    }
    DFS(0);
    for (int i = 1; i <= n; i++)
        printf("%d\n", sz[i]-1);
    return 0;
}