记录编号	158123	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 灾难	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.185 s
提交时间	2015-04-12 17:59:21	内存使用	8.87 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define N 66000
#define pos 17
int n,m,i,p,j,zj1,zj2,zj3,ans[N],L,R;
int to[N<<2],ne[N<<2],head[N],rehead[N],sj=1;
int dep[N],f[N][pos],ins[N],A[N];
inline void addedge(int u,int v)
{
	ins[v]++;to[++sj]=v,ne[sj]=head[u],head[u]=sj;
	to[++sj]=u,ne[sj]=rehead[v],rehead[v]=sj;
}
int TO[N],NE[N],HEAD[N],SJ;
inline void ADDEDGE(int u,int v)
{TO[++SJ]=v,NE[SJ]=HEAD[u],HEAD[u]=SJ;}

inline int lca(int u,int v)
{
 	if(dep[u]>dep[v])zj2=u,u=v,v=zj2;
 	if(dep[u]!=dep[v])
 	{
 		zj2=dep[v]-dep[u];
 		for(j=0;j<pos;j++)if(zj2&(1<<j))
 		v=f[v][j];
 	}
 	if(v!=u)
 	{
 		for(j=pos-1;j>=0;j--)
 		if(f[u][j]!=f[v][j])
 		u=f[u][j],v=f[v][j];
 		u=f[u][0];
 	}
 	return u;
}

void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&zj1);
		while(zj1)
		{
			addedge(zj1,i);
			scanf("%d",&zj1);
		}
		if(!ins[i])A[++R]=i;
	}
}
inline void DFS(int x)
{
	for(int h=HEAD[x];h;h=NE[h])
	if(TO[h]!=f[x][0])
	{
		DFS(TO[h]);
		ans[x]+=ans[TO[h]];
	}
	ans[x]++;
}
void work()
{
	while(L<R)
	{
		for(i=head[A[++L]];i;i=ne[i])
		if(!(--ins[to[i]]))A[++R]=to[i];
	}
	for(i=1;i<=n;i++)
	{
		if(rehead[A[i]])
			for(p=rehead[A[i]],zj1=to[p];p;p=ne[p])
			zj1=lca(zj1,to[p]);
		else zj1=n+1;
		
		ADDEDGE(zj1,A[i]);
		dep[A[i]]=dep[zj1]+1;
		f[A[i]][0]=zj1;
		for(p=1;p<pos;p++)f[A[i]][p]=f[f[A[i]][p-1]][p-1];
	}
	DFS(n+1);
}
int main()
{
	freopen("catas.in","r",stdin);
	freopen("catas.out","w",stdout);
	init();
	work();
	for(i=1;i<=n;i++)printf("%d\n",ans[i]-1);
	return 0;
}