「BZOJ2815」[ZJOI2012]灾难

Description

阿米巴是小强的好朋友。

阿米巴和小强在草原上捉蚂蚱。小强突然想,如果蚂蚱被他们捉灭绝了,那么吃蚂蚱的小鸟就会饿死,而捕食小鸟的猛禽也会跟着灭绝,从而引发一系列的生态灾难。

学过生物的阿米巴告诉小强,草原是一个极其稳定的生态系统。如果蚂蚱灭绝了,小鸟照样可以吃别的虫子,所以一个物种的灭绝并不一定会引发重大的灾难。

我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系:

一个食物网有NN个点,代表NN种生物,如果生物xx可以吃生物yy,那么从yyxx连一个有向边。

这个图没有环。

图中有一些点没有连出边,这些点代表的生物都是生产者,可以通过光合作用来生存; 而有连出边的点代表的都是消费者,它们必须通过吃其他生物来生存。

如果某个消费者的所有食物都灭绝了,它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为,如果它突然灭绝,那么会跟着一起灭绝的生物的种数。

举个例子:在一个草场上,生物之间的关系是:

如果小强和阿米巴把草原上所有的羊都给吓死了,那么狼会因为没有食物而灭绝,而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以,羊的灾难值是11。但是,如果草突然灭绝,那么整个草原上的55种生物都无法幸免,所以,草的灾难值是44

给定一个食物网,你要求出每个生物的灾难值。

Input

第一行是一个正整数 NN,表示生物的种数。生物从 11 标号到 NN
接下来 NN 行,每行描述了一个生物可以吃的其他生物的列表,格式为用空
格隔开的若干个数字,每个数字表示一种生物的标号,最后一个数字是 00 表示列表的结束。

Output

包含NN行,每行一个整数,表示每个生物的灾难值。

Sample Input

1
2
3
4
5
6
5
0
1 0
1 0
2 3 0
2 0

Sample Output

1
2
3
4
5
4
1
0
0
0

HINT

50%50\%的数据,N10000N \leq 10000
100%100\%的数据,1N655341 \leq N \leq 65534
输入文件的大小不超过1M1M。保证输入的食物网没有环。

Solution

ii行第jj列的数xx,表示iixx
如果xxyy,那么连边(y,x)(y,x)
fa[x]fa[x]表示如果fa[x]fa[x]死了,xx一定死。
假如考虑(u,v)(u,v)
如果vv的入度只有11,那么显然满足fa[v]=ufa[v]=u
如果vv的入度2\ge 2,那么fa[v]fa[v]就是所有与vv有边(u,v)(u,v)uuLCALCA
拓扑排序的过程动态建立树,LCALCA指的是新树上的LCALCA,原图是DAGDAG,不是树。

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
76
77
78
79
80
81
82
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 85534, M = 262144 * 3;
int s[N],d[N],f[N][25];
struct G {
int head[N], en;
struct Edge {
int u, v, nxt;
}e[M * 2];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int lca(int x, int y) {
if(d[x] < d[y]) swap(x, y);
for(int i = 20; ~i; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
for(int i = 20;~i; --i)
if(f[x][i] != f[y][i]) x= f[x][i], y = f[y][i];
return f[x][0];
}
void dfs(int x, int F) {
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
s[x] += s[y] + 1;
}
}
}g1,g2;
int t[N], cnt, ind[N], n, fa[N];
void topsort() {
queue<int>q;
for(int i = 1; i <= n; ++i) if(!ind[i]) q.push(i), fa[i] = n + 1;
for(int i = 0; i <= 20; ++i) f[n + 1][i] = n + 1;
while(!q.empty()) {
int x = q.front(); q.pop();
t[++cnt] = x;
d[x] = d[fa[x]] + 1;
f[x][0] = fa[x];
for(int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
g2.addedge(fa[x], x);
for(int i = g1.head[x]; i; i = g1.e[i].nxt) {
int y = g1.e[i].v;
if(!fa[y]) fa[y] = x;
else fa[y] = g2.lca(x, fa[y]);
if(!--ind[y]) q.push(y);
}
}
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
int j;
while(j = read()) {
g1.addedge(j, i); //i吃j
++ind[i];
}
}
topsort();
g2.dfs(n + 1, 0);
for(int i = 1; i <= n; ++i) writeln(s[i]);
return 0;
}