Description
阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：
如 
如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。
Input
第一行是一个正整数 N，表示生物的种数。生物从 1 标号到 N。
接下来 N 行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是 0 表示列表的结束。
Output
每行一个整数，表示每个生物的灾难值。
Sample Input
5
0
1 0
1 0
2 3 0
2 0Sample Output
3HINT
对50%的数据，N ≤ 10000。
对100%的数据，1 ≤ N ≤ 65534。
题目分析:
这题太强了 第一次知道灭绝树是什么东西 当年看到xqz博客里有这个题，完全就是为了读故事QAQ
灭绝树：一个点灭绝它的子树都会灭绝 那么每个动物的灾难值就是它的子树大小
那么我们将原图以食物->捕食者的顺序拓扑排序，为了保证到达一个点时，它的食物点都已经构建完成 。
接下来要构建灭绝树 我们想：如果一个动物灭绝了，那么它的食物一定都灭绝了，否则能找到其他食物。也就是说，这个动物的所有食物的LCA灭绝了。那我们求出每个点的食物在灭绝树里的LCA,将这个点与LCA连一条边。
将生产者的LCA看作是阳光 即再造一个0源点，连接所有生产者
最后DFS一次灭绝树，每个点的子树大小就是答案。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
queue<int>q;
int in[100005],num[100005];
int tota,totb;
int heada[2000005],headb[2000005];
struct your
{
int next,to;
}a[2000005],b[2000005];
int deep[100005],size[100005],fa[100005][20];
void adda(int x,int y)
{
a[++tota].next=heada[x];
a[tota].to=y;
heada[x]=tota;
in[y]++;
}
void addb(int x,int y)
{
b[++totb].next=headb[x];
b[totb].to=y;
headb[x]=totb;
}
void topsort()
{
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i);
while(q.size())
{
int nmp=q.front();
q.pop();
num[++num[0]]=nmp;
for(int i=heada[nmp];i;i=a[i].next)
if(!(--in[a[i].to])) q.push(a[i].to);
}
}
int kkk;
void Swp(int &x,int &y)
{
kkk=x,x=y,y=kkk;
return ;
}
int lca(int x,int y)
{
if(x==-1) return y;
if(deep[x]<deep[y]) Swp(x,y);
int temp=19;
while(temp>=0)
{
if(deep[fa[x][temp]]>=deep[y])
x=fa[x][temp];
temp--;
}
if(x==y) return x;
temp=19;
while(temp>=0)
{
if(fa[x][temp]!=fa[y][temp])
x=fa[x][temp],y=fa[y][temp];
temp--;
}
return fa[x][0];
}
void work(int x)
{
for(int i=1;i<=19;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
}
void dfs(int x,int temp)
{
for(int i=headb[x];i;i=b[i].next)
{
if(b[i].to==temp) continue;
dfs(b[i].to,x);
size[x]=size[x]+size[b[i].to]+1;
}
}
void build()
{
for(int i=num[0];i>=1;i--)
{
int Fa=-1;
for(int j=heada[num[i]];j;j=a[j].next)
Fa=lca(Fa,a[j].to);
if(Fa==-1) Fa=0;
addb(Fa,num[i]);
deep[num[i]]=deep[Fa]+1;
fa[num[i]][0]=Fa;
work(num[i]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
while(tmp!=0)
adda(i,tmp),scanf("%d",&tmp);
}
topsort();
build();
dfs(0,-1);
for(int i=1;i<=n;i++)
printf("%d\n",size[i]);
return 0;
}
