阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。 我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。
输入输出格式
输入格式： 输入文件 catas.in 的第一行是一个正整数 N，表示生物的种数。生物从 1 标 号到 N。 接下来 N 行，每行描述了一个生物可以吃的其他生物的列表，格式为用空 格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是 0 表示列表的结束。
输出格式： 输出文件catas.out包含N行，每行一个整数，表示每个生物的灾难值。
输入输出样例
输入样例#1： 5 0 1 0 1 0 2 3 0 2 0
输出样例#1： 4 1 0 0 0
【数据规模】
对50%的数据，N ≤ 10000。
对100%的数据，1 ≤ N ≤ 65534。
输入文件的大小不超过1M。保证输入的食物网没有环。
分析：首先，把食物网按从猎物到捕食者的顺序拓扑排序。依照top的序列构建灭绝树， 依次考虑每个生物i：假设我们已经构建好了排序在i之前的生物组成的“灭绝树”了。 假设i的食物有x[0]~x[k]（x[0]~x[k]在拓扑排序中比i靠前）， 很显然，只有x[0]~x[k]在树上的公共祖先的灭绝会导致i灭绝，否则i一定可以找到能让它活下来的食物。 于是，我们可以把i挂在x[0]~x[k]的最近公共祖先下面。 处理完所有的生物，我们得到的树就是整个图的灭绝树了。之后dfs计算一下每个节点对应的子树大小，子树大小-1即危险程度
注意：在利用倍增求LCA，维护爸爸时，我提供了两种写法，然而我发现我自己yy的写法（靠上的那个）要快，O(∩_∩)O~
这里写代码片 #include<cstdio> #include<cstring> #include<iostream> #include<cmath> using namespace std; const int N=65540; struct node{ int x,y,next; }; node way[N*4],way1[N*4],tree[N*4]; int in[N],out[N]; int sta[N],st[N],tot=0,tou,wei,tot1=0,st1[N],tot2=0,st2[N]; int ans[N],fa[N][40],n,deep[N],unit; void add(int u,int v) { tot++; way[tot].x=u; way[tot].y=v; way[tot].next=st[u]; st[u]=tot; return; } void add1(int u,int v) { tot1++; way1[tot1].x=u; way1[tot1].y=v; way1[tot1].next=st1[u]; st1[u]=tot1; return; } void add2(int u,int v) { tot2++; tree[tot2].x=u; tree[tot2].y=v; tree[tot2].next=st2[u]; st2[u]=tot2; return; } void top() //拓扑排序 { int i,j,tt=0; tou=0;wei=1; for (i=1;i<=n;i++) if (!in[i]) sta[wei++]=i,tt++; while (tt<n) { int r=sta[++tou]; for (i=st[r];i;i=way[i].next) { in[way[i].y]--; if (in[way[i].y]==0) { sta[wei++]=way[i].y; in[way[i].y]=N; tt++; } } } return; } int LCA(int u,int v) { int i; if (u==v) return u; if (deep[u]<deep[v]) swap(u,v); //默认u为较深的 int d=deep[u]-deep[v]; if (d) //不在同一深度 for (i=0;d;i++,d>>=1) //d转化为二进制 if (d&1) //这一位上是1 u=fa[u][i]; //向上跳 if (u==v) return u; for (i=unit;i>=0;i--) if (fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } return fa[u][0]; //直到跳到只有一步就重合了 ，返回 } void dfs(int x) //dfs利用灭绝树求子树size { ans[x]=1; int i; for (i=st2[x];i;i=tree[i].next) { dfs(tree[i].y); ans[x]+=ans[tree[i].y]; } } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { int u; scanf("%d",&u); while (u) { out[u]++;in[i]++; add(u,i);add1(i,u); //add用来top，add1用来添加反向变，辅助lca的求解 scanf("%d",&u); } } top(); unit=log(n)/log(2)+1; for (int i=1;i<=n;i++) //整个过程都要依靠top的结果~~~,从前向后 { int x=way1[st1[sta[i]]].y; for (int j=st1[sta[i]];j;j=way1[j].next) //通过反向边 x=LCA(x,way1[j].y); //寻找第i种生物所有食物的LCA add2(x,sta[i]); //i成为lca的儿子,建灭绝树 fa[sta[i]][0]=x; deep[sta[i]]=deep[x]+1; //不要忘了维护深度 for (int l=1;fa[fa[sta[i]][l-1]][l-1];l++) //维护倍增的爸爸,[]有点多，容易搞晕 fa[sta[i]][l]=fa[fa[sta[i]][l-1]][l-1]; //for (int k=x,l=0;fa[k][l];k=fa[k][l++]) 网上一个神犇的写法 //fa[sta[i]][l+1]=fa[k][l]; 这样的写法本蒟蒻这第一次见，nuibility } dfs(0); for (int i=1;i<=n;i++) printf("%d\n",ans[i]-1); return 0; }