Description：

给出一个食物网，求每个生物灭绝之后会有几个生物灭绝。

$1\leqslant n\leqslant 65534$

Solution：

如果我们能找出从每个点最靠后的灭绝会使他一起灭绝的生物，那么我们就可以建出来一棵树，这棵树上某个点的所有祖先无论哪个灭绝了他都会灭绝，那么我们最后要求的答案就是这棵树的子树大小。

思考怎么建这棵树，首先拓扑排序是肯定要有的，现在假设他拓扑排序之前的点所构成的树已经建好了，那么我们之后肯定是往这棵树上挂点，那么我们把这个点所有能吃的点在树中求一个 $LCA$ 就是最靠后的能使它灭绝的点，把他的父亲设成那个就行了。

树上加点求 $LCA$ 可以动态构建倍增数组做。

其实这就是支配树在 $DAG$ 上的特殊情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 65536

int f[MAXN][17];

int deg[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN * 4];

int edgenum = 0;

int lin[MAXN] = {0};

vector<int> g[MAXN];

void add(int a,int b)

{

	++deg[b];g[b].push_back(a);

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int siz[MAXN];

int dep[MAXN];

int LCA(int a,int b)

{

	if(dep[a] < dep[b])swap(a,b);

	for(int i = 16;i >= 0;--i)

	{

		if(dep[f[a][i]] >= dep[b])

			a = f[a][i];

	}

	if(a == b)return a;

	for(int i = 16;i >= 0;--i)

	{

		if(f[a][i] != f[b][i])

		{

			a = f[a][i];

			b = f[b][i];

		}

	}

	a = f[a][0];b = f[b][0];

	return a;

}

void build(int k)

{

	int lca = g[k][0];

	for(int i = 1;i < g[k].size();++i)lca = LCA(lca,g[k][i]);

	f[k][0] = lca;

	dep[k] = dep[lca] + 1;

	for(int i = 1;i <= 16;++i)

	{

		f[k][i] = f[f[k][i - 1]][i - 1];

	}

	return;

}

vector<int> m[MAXN];

void dp(int k)

{

	siz[k] = 1;

	for(vector<int>::iterator i = m[k].begin();i != m[k].end();++i)

	{

		dp(*i);

		siz[k] += siz[*i];

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a;

	for(int i = 1;i <= n;++i)

		while((a = read()) != 0)add(a,i);

	queue<int> q;

	for(int i = 1;i <= n;++i)

	{

		if(deg[i] == 0)

		{

			q.push(i);dep[i] = 1;

			add(0,i);

		}

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			--deg[e[i].to];

			if(deg[e[i].to] == 0)

			{

				build(e[i].to);

				q.push(e[i].to);

			}

		}

	}

	for(int i = 1;i <= n;++i)m[f[i][0]].push_back(i);

	dp(0);

	for(int i = 1;i <= n;++i)printf("%d\n",siz[i] - 1);

	return 0;

}