好像很久之前就看过这道题，大概是刚学\(LCA\)的时候

之后当时肯定是不会的呀

现在发现这道题并不是非常难

首先我们发现这个灭绝的关系非常像一棵树，我们建出这个灭绝树求一个前缀和就可以啦

那么应该怎么建这棵树呢

我们一边拓扑排序一边建树，一个点的父亲应该是其所有食物节点的\(lca\)，于是一边拓扑排序一边求\(lca\)就好了

手滑了好几次

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define re register

#define maxn 70005

struct Edge

{

	int v,nxt;

}e[200005];

int head[maxn];

int num,n;

inline void add_edge(int x,int y)

{

	e[++num].v=y;

	e[num].nxt=head[x];

	head[x]=num;

}

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int deep[maxn],f[maxn][18];

namespace Topsort

{

	struct E

	{

		int v,nxt;

	}e[200005];

	int num,head[maxn],r[maxn],q[maxn];

	int fa[maxn];

	inline void add(int x,int y)

	{

		e[++num].v=y;

		e[num].nxt=head[x];

		head[x]=num;

	}

	inline int LCA(int x,int y)

	{

		if(deep[x]<deep[y]) std::swap(x,y);

		for(re int i=17;i>=0;--i)

		if(f[x][i]!=-1&&deep[f[x][i]]>=deep[y]) x=f[x][i];

		if(x==y) return x;

		for(re int i=17;i>=0;i--)

		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

		return f[x][0];

	}

	inline void init()

	{

		n=read();

		int x;

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

		{

			x=read();

			while(x) add(x,i),r[i]++,x=read();

		}

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

		if(!r[i]) add(0,i),r[i]++;

		int tot=0;

		q[++tot]=0;

		memset(f,-1,sizeof(f));

		memset(fa,-1,sizeof(fa));

		for(re int i=1;i<=tot;i++)

		{

			for(re int j=head[q[i]];j;j=e[j].nxt)

			{

				r[e[j].v]--;

				if(fa[e[j].v]==-1) fa[e[j].v]=q[i];

				else fa[e[j].v]=LCA(fa[e[j].v],q[i]);

				if(!r[e[j].v])

				{

					add_edge(fa[e[j].v],e[j].v);

					deep[e[j].v]=deep[fa[e[j].v]]+1;

					f[e[j].v][0]=fa[e[j].v];

					for(re int k=1;k<=17;k++)

						f[e[j].v][k]=f[f[e[j].v][k-1]][k-1];

					q[++tot]=e[j].v;

				}

			}

		}

	}

}

int sz[maxn];

void dfs(int x)

{

	sz[x]=1;

	for(re int i=head[x];i;i=e[i].nxt)

	if(deep[e[i].v]>deep[x])

	{

		deep[e[i].v]=deep[x]+1;

		dfs(e[i].v);

		sz[x]+=sz[e[i].v];

	}

}

int main()

{

	Topsort::init();

	dfs(0);

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

		printf("%d\n",sz[i]-1);

	return 0;

}