#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=4e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,Siz[maxn]; int fa[maxn],dfn[maxn],siz[maxn],top[maxn],bot[maxn],son[maxn],dep[maxn],idfn[maxn],cnt; vector<pi>Q[maxn]; vector<int>E[maxn]; int lst[maxn],deg[maxn],del[maxn]; ll ans[maxn]; struct nd {int op,x;}d[maxn]; inline void add(int x,int l,int r){if(l<=r)Q[x].p_b(m_p(l,r));} int rt[maxn]; ll t[maxn]; inline void Add(int l,int r,ll x){t[l]+=x,t[r+1]-=x;} namespace DS { struct nd { int ls,rs,mx,se; pi lz1;ll lz2;int lz3; nd(){lz2=lz3=0,lz1.p1=lz1.p2=0;} void push(pi A,ll B,int C){ if(C==-1)return; if(lz3==-1){ lz3=C; }else { lz2+=(C-lz1.p2)*1ll*lz1.p1; } mx=A.p1,lz1=A; lz2+=B; } }d[maxn*30]; int stk[maxn*30],top; int cnt; #define ls(p) d[p].ls #define rs(p) d[p].rs void pu(int p){ if(d[ls(p)].mx==d[rs(p)].mx)d[p].mx=d[ls(p)].mx,d[p].se=max(d[ls(p)].se,d[rs(p)].se); else if(d[ls(p)].mx>d[rs(p)].mx)d[p].mx=d[ls(p)].mx,d[p].se=max(d[ls(p)].se,d[rs(p)].mx); else d[p].mx=d[rs(p)].mx,d[p].se=max(d[ls(p)].mx,d[rs(p)].se); } inline int nnd(){ int p=top?stk[top--]:(++cnt); ls(p)=rs(p)=0,d[p].mx=1e9,d[p].se=-1; d[p].lz1=m_p(1e9,0),d[p].lz2=0,d[p].lz3=0; return p; } void pd(int p){ if(!ls(p))ls(p)=nnd(); if(!rs(p))rs(p)=nnd(); if(d[p].lz3==-1)return; int mx=max(d[ls(p)].mx,d[rs(p)].mx); auto _=[&](int k){ if(d[k].mx>d[p].lz1.p1)d[k].push(d[p].lz1,d[p].lz2,d[p].lz3); }; _(ls(p)),_(rs(p)); d[p].lz1=m_p(-1,-1),d[p].lz2=0; d[p].lz3=-1; } void modify(int l,int r,int s,int t,int &p,pi k){ if(!p)p=nnd(); if(l<=s&&t<=r){ if(d[p].mx<=k.p1)return; if(d[p].se<k.p1){ return d[p].push(k,0,k.p2),void(); } }pd(p);int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),k);if(r>mid)modify(l,r,mid+1,t,rs(p),k);pu(p); } void solve(int s,int t,int p,int tim){ if(!ls(p))return Add(s,t,d[p].lz2+(tim-d[p].lz1.p2)*1ll*d[p].lz1.p1);pd(p); int mid=s+t>>1; solve(s,mid,ls(p),tim),solve(mid+1,t,rs(p),tim); } void print(int s,int t,int p,int tim){ //cout<<"test "<<p<<" "<<d[p].lz1.p1<<endl; if(s==t)return cout<<d[p].lz2+(tim-d[p].lz1.p2)*1ll*d[p].lz1.p1<<" ",void();pd(p); int mid=s+t>>1; print(s,mid,ls(p),tim),print(mid+1,t,rs(p),tim);pu(p); } void del(int s,int t,int p){ stk[++top]=p; if(!ls(p))return; int mid=s+t>>1; del(s,mid,ls(p)),del(mid+1,t,rs(p)); } } void dfs(int u){ siz[u]=1,Siz[u]=Q[u].size()+1; for(int x:E[u])dfs(x),siz[u]+=siz[x],Siz[u]+=Siz[x],son[u]=(Siz[x]>Siz[son[u]])?x:son[u]; } inline int Bot(int u){return bot[top[u]];} void dfs2(int u,int tp){ idfn[dfn[u]=++cnt]=u,top[u]=tp,bot[tp]=u; if(!son[u])return; dfs2(son[u],tp); for(int x:E[u])if(x!=son[u])dfs2(x,x); } void ins(int u,int &rt,int tim){ up(i,dfn[u],dfn[u]+siz[u]-1)for(auto it:Q[idfn[i]]){ DS::modify(it.p1,it.p2,1,n,rt,m_p(dep[idfn[i]],tim)); } } void dfs3(int u){ if(son[u])dfs3(son[u]),rt[u]=rt[son[u]]; for(int x:E[u])if(x!=son[u])dfs3(x),DS::solve(1,n,rt[x],dep[Bot(x)]-dep[u]),DS::del(1,n,rt[x]); for(int x:E[u])if(x!=son[u])ins(x,rt[u],dep[Bot(u)]-dep[u]); for(auto it:Q[u])DS::modify(it.p1,it.p2,1,n,rt[u],m_p(dep[u],dep[Bot(u)]-dep[u])); if(u==1)DS::solve(1,n,rt[u],dep[Bot(u)]-dep[u]+1); } void slv(){ n=read(),m=1; up(i,1,n)d[i].op=read(),d[i].x=read(),m+=d[i].op==1; int cnt=1; lst[1]=1,dep[1]=1; ll sd=1,sc=1; up(i,1,n){ int op=d[i].op,x=d[i].x; if(op==1){ if(!deg[x])add(x,lst[x],i-1); ++cnt;E[x].p_b(cnt);fa[cnt]=x,dep[cnt]=dep[x]+1; sd+=dep[cnt],sc++; lst[cnt]=i,++deg[x]; } else { sd-=dep[x],sc--;add(x,lst[x],i-1);del[x]=1; if(!(--deg[fa[x]]))lst[fa[x]]=i; } ans[i]-=(m-sc)*1ll*int(1e9); ans[i]-=sd; } up(i,1,m)if((!deg[i])&&(!del[i]))add(i,lst[i],n); dfs(1);dfs2(1,1);dfs3(1); up(i,1,n)t[i]+=t[i-1]; up(i,1,n)ans[i]+=t[i]; up(i,1,n)printf("%lld\n",ans[i]); } int main(){ //freopen("leftish.in","r",stdin),freopen("leftish.out","w",stdout); slv(); return 0; }