【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
    
     #define ll long long#define N 70005using 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
     
      r[N];int in[N];queue
      
       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]
       
        =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
        
         =1;i--) {        int now=st[i];        size[now]++;        size[fa[now][0]]+=size[now];    }    for(int i=1;i<=n;i++) cout<
         
          <<"\n"; return 0;}