时光机TimeMachine

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 35524+100;
int n,m,du[N],size[N];
int scan(){int i=0;scanf("%d",&i);return i;}
struct Node{
	Node();
	Node *ch[2],*fa;int flag,d;
	bool pl(){return this == fa->ch[1];flag=0;}
	void push();
}*null,lnode[N];
Node::Node(){ch[0]=ch[1]=fa=null;}
void Node::push(){
	if(flag){
		swap(ch[0],ch[1]);
		ch[0]->flag^=1;
		ch[1]->flag^=1;
		flag=0;
	}
}
struct LCT{
	LCT(){
		if(!null){
			null = new Node();
			*null = Node();
		}
	}
	bool notr(Node *r){return r->fa->ch[0]==r || r->fa->ch[1]==r;}
	void rotate(Node *k){
		Node *r = k->fa;if(r==null||k==null)return;
		r->push();k->push(); //*
		int x = k->pl()^1;
		r->ch[x^1] = k->ch[x];
		r->ch[x^1]->fa = r;
		if(r->fa!=null&&notr(r))r->fa->ch[r->pl()]=k;//*
		k->fa = r->fa;r->fa = k;
		k->ch[x] = r;
	}
	void splay(Node *r){
		for(;notr(r);rotate(r))
		if(notr(r->fa))rotate(r->fa->pl()==r->pl()?r->fa:r);
		r->push();
	}
	Node *hello(Node *r){
		Node *l = null;
		for(;r!=null;l=r,r=r->fa){
			splay(r);
			(r->ch[1]=l)->fa = r;
			//r->count();
		}return l;
	}
	void changer(Node *r){
		hello(r)->flag^=1;
		splay(r);
	}
	void link(Node *r,Node *l){
		changer(r);
		r->fa = l;
		//splay(r);//!!!
		hello(r);//*
	}
	void cut(Node *r,Node *l){//?
		changer(r);
		hello(l);
		splay(r);
		r->ch[1]=l->fa=null;
	}
	int lca(Node *r,Node *l,Node *ro){
		changer(ro);
		hello(r);
		return hello(l)->d;
	}
}lt;
struct Point{
	Point(){next = NULL;}
	int d;Point*next;
	void push(int a){
		Point *l = new Point;
		l->d = a;
		l->next = next;next=l;
	}
}point[N],tree[N],eat[N];
void link(int a,int b){
	//printf("%d->%d\n",a,b);
	lt.link(&lnode[a],&lnode[b]);
	tree[a].push(b);
}
queue<int>dui;
void dfs(int x){
	size[x]=1;
	for(Point *i = tree[x].next;i!=NULL;i=i->next){
		dfs(i->d);
		size[x] += size[i->d];
	}
}
int main(){
	int i,j,a;
	//freopen("in.txt","r",stdin);
	n = scan();
	for(i=1;i<=n+1;i++)lnode[i] = Node(),lnode[i].d=i;
	for(i=1;i<=n;i++){
		a = scan();
		while(a){
			point[a].push(i);
			eat[i].push(a);
			du[i]++;
			a = scan();
		}
		if(!du[i]){
			eat[i].push(n+1);
			dui.push(i);
			//printf("%d\n",i);
		}
	}
	while(!dui.empty()){
		int now = dui.front();dui.pop();
		//printf("%d ",now);
		//each eat
		a = eat[now].next->d;
		for(Point *l = eat[now].next;l!=NULL;l=l->next)
			a = lt.lca(&lnode[a],&lnode[l->d],&lnode[n+1]);
		//printf("[%d]\n",a);
		link(a,now);
		//each hunter
		for(Point *l = point[now].next;l!=NULL;l=l->next){
			du[l->d]--;
			if(!du[l->d])dui.push(l->d);
		}
	}
	dfs(n+1);
	for(i=1;i<=n;i++)
	printf("%d\n",size[i]-1);
	return 0;
}