Description

Input

Output

Sample Input

Sample Output

HINT

好题！（Q：你TM每一道题都是好题？A：= =谁叫我太弱辣）

感觉做法这的好神啊，首先可以想什么时候一个物种A会灭绝

1.这个物种只有一种食物，而这个食物灭绝了。

2.这个物种有多个食物，这些食物都灭绝了。

好像什么都没说啊= =

好吧我们把情况2继续拓展。

这多个食物同时灭绝，说明在这些食物的食物子系中有个共同点，而这个点灭绝了（必要条件）

好像有点绕= =

反正说这么多就是说 我们可以构造出一棵灭绝树，一个物种的灭绝会导致其所有子树灭绝。

那应该怎么构造这棵树呢！

因为不能画图，所以只能用伪代码来解释了（= =大家自己可以手画一下）

add(1,2);add(1,3);add(2,4);add(3,4);add(2,5);（就是样例）

有向边x->y表示x是y的食物。

首先 1灭绝，会导致2,3的灭绝，那就在灭绝树上insert(1,2),insert(1,3)

然后2的灭绝会导致5的灭绝，insert(2,5);

考虑4，他有两种食物2,3，那么他灭绝应该当且仅当1（2,3的子系的共同点）灭绝时，insert（1,4）

其实这个共同点就是灭绝树上的LCA

可以先做一个拓扑，这样之后，可以保证物种i加入树时，他的食物已全部加入，灭绝树上。

所以就可以用倍增LCA，而不是LCT了

代码如下

#include <cstdio>
#include <queue>
#define maxn 70000
#define maxm 2000010
using namespace std;
queue<int> q;
int n,size[maxn],vis[maxn],head[maxn],tail[maxn],f[maxn][21],rd[maxn],b[maxn],st[maxn],deep[maxn];
int last[maxm],nxt[maxm],h[maxm],v[maxm],len,l;
void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}
void insert(int x,int y)
{
	v[++l] = y;
	nxt[l] = tail[x];
	tail[x] = l;
//	printf("%d->%d\n",x,y); 
}

void tp()
{
	for (int i = 1;i <= n;i++)
	if (!rd[i])q.push(i);
	for (;!q.empty();)
	{
		int x = q.front();
		b[x] = 1;
		q.pop();
		st[++len] = x;
		for (int i = head[x];i;i = last[i])
		if (--rd[h[i]]<=0)q.push(h[i]);
	}
}
int LCA(int x,int y)
{
	if(x==-1)return y;
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;(1<<i)<=t;i++)
        if(t&(1<<i))x=f[x][i];
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    if(x==y)return x;
    return f[x][0];
}
void pre(int x)
{
    for(int i=1;(1<<i)<=deep[x];i++)
        f[x][i]=f[f[x][i-1]][i-1];
}
void Build()
{
	for (int i = len;i >= 1;i--)
	{
		int fa = -1;
		for (int j = head[st[i]];j;j = last[j])
			fa = LCA(fa,h[j]);
		if (fa == -1) fa = 0;
		insert(fa,st[i]);
		deep[st[i]] = deep[fa]+1;
        f[st[i]][0] = fa;
        pre(st[i]);
    }
}
void dfs(int x)
{
	size[x] = vis[x] = 1;
	for (int i = tail[x];i;i = nxt[i])
		if (!vis[v[i]])
		{
			dfs(v[i]);
			size[x] += size[v[i]];
		}
}

int main()
{
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
		for (int x;scanf("%d",&x)&&x;add(i,x),rd[x]++);
	tp();
	l = 0;
	Build();
	dfs(0);
	for (int i = 1;i <= n;i++)
		printf("%d\n",size[i]-1);
	return 0;
}

离省选爆零越来越近了，还是多艹点题，争取拿10分暴力！