#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 lst,lz1;ll lz2;int lz3; void push(pi A,ll B,int C){ if(C==-1)return; if(lz3==-1)lz3=C; if(lz1.p1>=0)lz2+=(C-lst.p2)*1ll*lz1.p1,lst=A; mx=A.p1,lz1=A; lz2+=B; } }d[maxn*30]; 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; 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=++cnt; ls(p)=rs(p)=0,d[p].mx=1e9,d[p].se=0; 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(); int mx=max(d[ls(p)].mx,d[rs(p)].mx); auto _=[&](int k){ if(d[k].mx==mx)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){ 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 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); } vector<pair<pi,int> >range; void ins(int u){ up(i,dfn[u],dfn[u]+siz[u]-1)for(auto it:Q[idfn[i]]){ range.p_b(m_p(m_p(it.p1,it.p2),dep[idfn[i]])); //if(fa[u]==1)cout<<"add "<<it.p1<<" "<<it.p2<<" "<<dep[idfn[i]]<<endl; //DS::modify(it.p1,it.p2,1,n,rt,m_p(dep[idfn[i]],tim)); //if(fa[u]==1)DS::print(1,n,rt,dep[Bot(fa[u])]-dep[fa[u]]+1),cout<<endl; } } 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]); range.clear(); for(int x:E[u])ins(x); for(auto it:Q[u])range.p_b(m_p(m_p(it.p1,it.p2),dep[u])); vector<int>vec; for(auto it:range)vec.p_b(it.p1.p1-1),vec.p_b(it.p1.p2); sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); vector<vector<int> >add(vec.size()); multiset<int>S; for(auto it:range){ int l=lower_bound(vec.begin(),vec.end(),it.p1.p1)-vec.begin(); add[l].p_b(it.p2); int r=lower_bound(vec.begin(),vec.end(),it.p1.p2)-vec.begin(); if(r+1<vec.size())add[r+1].p_b(-it.p2); } up(i,1,(int)vec.size()-1){ for(int x:add[i]){ if(x>0)S.insert(x); else S.erase(S.lower_bound(-x)); } if(!S.empty()) DS::modify(vec[i-1]+1,vec[i],1,n,rt[u],m_p(*S.begin(),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; }