#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&¬r(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;
}
评论