【ZJOI2012】灾难
阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有 N个点，代表 N 种生物，如果生物 x 可以吃生物 y，那么从 y向 x 连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：
如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是 1。但是，如果草突然灭绝，那么整个草原上的 $5 $种生物都无法幸免，所以，草的灾难值是 4。
给定一个食物网，你要求出每个生物的灾难值。
输入的第一行是一个正整数 N，表示生物的种数。生物从 1 标号到 N。
接下来 N 行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是 0 表示列表的结束。
输出包含N行，每行一个整数，表示每个生物的灾难值。
样例输入
5
0
1 0
1 0
2 3 0
2 0
样例输入
4
1
0
0
0
灭绝树。\(v\)的父亲\(u\)，如果将\(u\)消灭，那么\(v\)也会被消灭。
求\(DAG\)的灭绝树先\(top\)排序，然后对于点\(v\)，找它所有入边的起点，求这些起点的\(lca\)就是\(v\)的父亲。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 70005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n;
struct road {
int to,next;
}s[N<<3];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
vector<int>r[N];
int in[N];
queue<int>q;
int st[N];
int fa[N][20],dep[N];
void top_sort() {
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
while(!q.empty()) {
int v=q.front();q.pop();
st[++st[0]]=v;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(!(--in[to])) q.push(to);
}
}
}
int lca(int a,int b) {
if(dep[a]<dep[b]) swap(a,b);
for(int i=16;i>=0;i--)
if(fa[a][i]&&dep[fa[a][i]]>=dep[b])
a=fa[a][i];
if(a==b) return a;
for(int i=16;i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
int size[N];
int main() {
n=Get();
for(int i=1;i<=n;i++) {
int a;
while(a=Get(),a) {
add(a,i);
r[i].push_back(a);
in[i]++;
}
}
top_sort();
for(int i=1;i<=st[0];i++) {
int now=st[i];
int t=-1;
for(int j=0;j<r[now].size();j++) {
int f=r[now][j];
if(t==-1) t=f;
else t=lca(t,f);
}
if(t==-1) fa[now][0]=0;
else fa[now][0]=t;
dep[now]=dep[fa[now][0]]+1;
for(int j=1;j<=16;j++) fa[now][j]=fa[fa[now][j-1]][j-1];
}
for(int i=n;i>=1;i--) {
int now=st[i];
size[now]++;
size[fa[now][0]]+=size[now];
}
for(int i=1;i<=n;i++) cout<<size[i]-1<<"\n";
return 0;
}