#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/44104163");
}原题面请见
http://www.cnblogs.com/JS-Shining/archive/2013/01/12/2857429.html
我们构建1颗灾害树，使得1个节点的任意1个先人灭绝，则其会灭绝。
则可以依照拓扑序扫每一个节点，然后加入到灾害树中时只需要把它的父亲赋成它所有食品的LCA就行了。
我们可以动态处理每一个节点的倍增lca数组
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 70000
#define M 600000
#define LOGN 20
using namespace std;
struct KSD
{
int v,next;
}e[M],E[M],Ee[M];
int head[N],cnt,HEAD[N],CNT,Head[N];
inline void add(int u,int v)
{
e[++cnt].v=v;
Ee[cnt].v=u;
e[cnt].next=head[u];
Ee[cnt].next=Head[v];
Head[v]=head[u]=cnt;
}
inline void ADD(int u,int v)
{
E[++CNT].v=v;
E[CNT].next=HEAD[u];
HEAD[u]=CNT;
}
int f[N][LOGN],dep[N];
int getlca(int a,int b)
{
int i;
if(dep[a]<dep[b])swap(a,b);
for(i=LOGN-1;i>=0;i--)
if(dep[f[a][i]]>=dep[b])a=f[a][i];
if(a==b)return a;
for(i=LOGN-1;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
int d[N],ans[N];
queue<int>q;
int dfs(int x)
{
ans[x]=1;
for(int i=HEAD[x];i;i=E[i].next)
ans[x]+=dfs(E[i].v);
return ans[x];
}
int n;
int main()
{
int i,j,k;
int a,b,c;
int u,v,lca;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
while(scanf("%d",&a),a)
{
add(a,i);
d[i]++;
}
}
for(i=1;i<=n;i++)if(!d[i])add(n+1,i),d[i]=1;
q.push(n+1);
while(!q.empty())
{
u=q.front(),q.pop();
lca=0;
for(i=Head[u];i;i=Ee[i].next)
{
v=Ee[i].v;
if(i==Head[u])lca=v;
else lca=getlca(lca,v);
}
for(i=head[u];i;i=e[i].next)
{
d[v=e[i].v]--;
if(!d[v])q.push(v);
}
if(lca)
{
ADD(lca,u),f[u][0]=lca;
for(j=1;j<LOGN;j++)
f[u][j]=f[f[u][j-1]][j-1];
}
dep[u]=dep[lca]+1;
}
dfs(n+1);
for(i=1;i<=n;i++)printf("%d
",ans[i]-1);
return 0;
}