本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ2815
正解：倍增+拓扑排序
解题报告：
考虑一种动物如果会被灭绝当且仅当他的所有食物都灭绝了，那么只要有一个没被灭绝他就能存活下来，不难想到，我只要求出了他的所有食物的$lca$，那个点就是能灭绝他的最近的点。
为了方便我们设置一个超级源点，能吃掉所有的生产者，那么我对原图做一遍拓扑排序，根据能灭绝他的最近的点建出一张新的图，容易发现新的图是一棵树（支配树？），边拓扑排序边连边，边求$lca$，最后$dfs$一遍，对每个点求一遍$size$就可以得到答案了。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 100011;
const int MAXM = 200011;
int n,ecnt,first[MAXN],next[MAXM],to[MAXM];
int f[MAXN][17],in[MAXN],deep[MAXN],size[MAXN];
queue<int>q;
vector<int>w[MAXN],pre[MAXN];
inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; pre[y].push_back(x); }
inline void Link(int x,int y){ w[x].push_back(y); f[y][0]=x; deep[y]=deep[x]+1; for(int i=1;i<=16;i++) f[y][i]=f[f[y][i-1]][i-1]; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y); int t=0; while((1<<t)<=deep[x]) t++; t--;
for(int i=t;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=f[x][i]; if(x==y) return x;
for(int i=t;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];
}
inline void topo_sort(){
deep[n+1]=1;
for(int i=1;i<=n;i++)
if(in[i]==0)
Link(n+1,i),q.push(i);
int u,fa;
while(!q.empty()) {
u=q.front(); q.pop();
for(int i=first[u];i;i=next[i]) {
int v=to[i];
in[v]--;
if(in[v]==0) {
fa=pre[v][0]; q.push(v);
for(int j=1,ss=pre[v].size();j<ss;j++)
fa=lca(fa,pre[v][j]);
Link(fa,v);
}
}
}
}
inline void dfs(int x){
size[x]=1;
for(int i=0,ss=w[x].size();i<ss;i++) {
int v=w[x][i];
dfs(v);
size[x]+=size[v];
}
}
inline void work(){
n=getint(); int x;
for(int i=1;i<=n;i++) {
x=getint();
while(x>0) {
link(x,i); in[i]++;
x=getint();
}
}
topo_sort();
dfs(n+1);
for(int i=1;i<=n;i++)
printf("%d\n",size[i]-1);
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
原文：http://www.cnblogs.com/ljh2000-jump/p/6517318.html