BZOJ2815 [ZJOI2012] 灾难

Description

\(n\) 个点 \(m\) 条边的DAG,对于每个点,求它的重要度。重要度定义如下:

对于 \(v\) 这个点,将其(和其相连的所有边)删去。之后考察所有点,如果某个点初始时出度不为 \(0\) 而当前出度为 \(0\) ,则将这个点也删去。重复这个过程直到没有点被删去。 \(v\) 的重要度即为除它以外删掉的点的个数。

\(n\leqslant10^5\)

Solution

首先我们把所有边都反向(这样比较方便处理,其实也无所谓的)。

这样的话,拓扑序后面的点不会影响到前面的点。

首先,我们有一个性质: \(u\) 会影响到 \(v\) 当且仅当所有从生产者到 \(v\) 的路径上都包含 \(u\) 。这是显然的。

对于一个点 \(v\) ,找到会影响到它的点(也就是说,那些删掉之后会导致 \(v\) 消失)中除了它本身外拓扑序最靠后的一个点,假设它是 \(t_v\)

那么有一个重要的性质:会影响到 \(v\) 的点只有 \(v, t_v, t_{t_v}, ...\) 这些。

证明:

如果有某个点 \(u\) 会影响到 \(v\) ,它在拓扑序上必定位于某个 \(t_k\)\(k\) 之间,其中 \(k=t_{\ddots_v}\)

既然 \(t_k\) 是最后一个能影响到 \(k\) 的,那么 \(u\) 就不能影响到 \(k\) 。那么一定存在一条从生产者到 \(k\) 的路径不经过 \(u\) 。但是既然 \(k\) 会影响到 \(v\) ,就一定存在一条 \(k\)\(v\) 的路径。把这两条路径拼起来,就能得到一条从生产者到 \(v\) 、不经过 \(u\) 的路径,于是 \(u\) 就不能影响到 \(v\) ,矛盾。

那么我们把 \(t\) 当成父亲关系建出一棵树(即“灭绝树”),删掉 \(v\) 之后受影响的结点个数就是 \(v\) 的子树大小。所以现在只需要考虑 \(t\) 怎么求。

按拓扑序建树,则考虑到某个点的时候它的前驱已经考虑完了。那么它的父亲就会是它所有的前驱的 LCA (因为只有删掉公共祖先才能使这些前驱都被删掉,从而使 v 被删掉)。

边建树边倍增即可。复杂度 \(O(n\log n)\)

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
69
70
71
72
73
74
75
#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 100050;
const int M = 1000050;

int pre[N], to[M], nxt[M], cnt;
int n, m, f[N], fa[N][20], dep[N], ind[N];
int que[N], siz[N];

inline void addEdge(int x, int y) {
nxt[cnt] = pre[x];
to[pre[x] = cnt++] = y;
}

int LCA(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (int i = 19; i >= 0; --i)
if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
for (int i = 19; i >= 0; --i)
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
return x == y ? x : f[x];
}

void Build(int x) {
dep[x] = 1 + dep[fa[x][0] = f[x]];
for (int i = 0; fa[x][i] != 0; ++i)
fa[x][i + 1] = fa[fa[x][i]][i];
}

int main() {
scanf("%d", &n);
memset(pre, -1, sizeof pre);

for (int x = 1; x <= n; ++x)
for (int y; ; ) {
scanf("%d", &y);
if (y == 0) break;
addEdge(y, x);
++ind[x];
}

int hd = 0, tl = 0;
memset(f, -1, sizeof f);
for (int i = 1; i <= n; ++i)
if (ind[i] == 0) {
dep[i] = 1;
f[i] = 0;
que[tl++] = i;
}

while (hd < tl) {
int x = que[hd++];
for (int i = pre[x]; i != -1; i = nxt[i]) {
int y = to[i];
if (f[y] == -1)
f[y] = x;
else if (f[y] != 0)
f[y] = LCA(f[y], x);
if ((--ind[y]) == 0)
Build(que[tl++] = y);
}
}

for (int i = n - 1; i >= 0; --i)
siz[f[que[i]]] += ++siz[que[i]];
for (int i = 1; i <= n; ++i)
printf("%d\n", siz[i] - 1);
return 0;
}