768G - The Winds of Winter - CodeForces Solution

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,ex,ey,fa[N];
struct node{
	int nxt;int to;
}e[N];
int head[N],tot;
int dfn[N],idfn[N],sz[N],idx; 
int ans[N],rt;
inline void read(int &x)
{
	int f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
}
inline int mn(int _x,int _y){return _x<_y?_x:_y;}
inline int mx(int _x,int _y){return _x>_y?_x:_y;}
inline int ab(int _x){return _x<0?-_x:_x;}

inline void add(int from,int to){
	e[++tot].to=to;e[tot].nxt=head[from];head[from]=tot; 
}

inline void dfs1(int x){
	dfn[x]=(++idx);idfn[idx]=x;sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		dfs1(v);
		sz[x]+=sz[v];
	}
	return ;
} 

int ls[N*30],rs[N*30],cnt[N*30],Ncnt;
int root[N];
inline int cpy(int x){
	++Ncnt;ls[Ncnt]=ls[x];rs[Ncnt]=rs[x];
	cnt[Ncnt]=cnt[x];return Ncnt;
}
inline int ins(int x,int l,int r,int pos){
	x=cpy(x); ++cnt[x];
	if(l==r) return x;
	int mid=l+r>>1;
	if(pos<=mid) ls[x]=ins(ls[x],l,mid,pos);
	if(pos>mid) rs[x]=ins(rs[x],mid+1,r,pos);
	return x;
}
inline int query(int x,int l,int r,int ql,int qr){
	if(x==0||ql>qr) return 0;
	if(ql<=l&&r<=qr) return cnt[x];
	int mid=l+r>>1,res=0;
	if(ql<=mid) res+=query(ls[x],l,mid,ql,qr);
	if(qr>mid) res+=query(rs[x],mid+1,r,ql,qr);
	return res;	
}
inline int Q(int dl,int dr,int l,int r){
	if(dl>dr||l>r) return 0;
	return query(root[dr],1,n,mx(l,0),mn(r,n))-query(root[dl-1],1,n,mx(l,0),mn(r,n));
}

struct Segment{
	int cnt[N*4];
	inline void pushup(int x){
		cnt[x]=cnt[x<<1]+cnt[x<<1|1];
		return ;
	}
	inline void update(int x,int l,int r,int pos,int v){
		if(l==r){cnt[x]+=v;return ;}
		int mid=l+r>>1;
		if(pos<=mid) update(x<<1,l,mid,pos,v);
		if(pos>mid) update(x<<1|1,mid+1,r,pos,v);
		pushup(x);return ;
	}
	inline int query(int x,int l,int r,int ql,int qr){
		if(ql>qr) return 0;
		if(ql<=l&&r<=qr) return cnt[x];
		int mid=l+r>>1,res=0;
		if(ql<=mid) res+=query(x<<1,l,mid,ql,qr);
		if(qr>mid) res+=query(x<<1|1,mid+1,r,ql,qr);
		return res;
	}
}S;

inline void upd(int &firmx,int &secmx,int &mxid,int sz,int id){
	if(sz>=firmx){secmx=firmx;firmx=sz;mxid=id;}
	else secmx=mx(secmx,sz);
	return ;
}
inline void Solve(int x){
	int deg=(x!=rt);
	for(int i=head[x];i;i=e[i].nxt) ++deg;
	if(deg<=1){ans[x]=n-1;return ;}
	int firmx=-1,secmx=-1,mxid=-1,mnsz=1000000000;
	if(x!=rt) {upd(firmx,secmx,mxid,n-sz[x],-1);mnsz=mn(mnsz,n-sz[x]);}
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		upd(firmx,secmx,mxid,sz[v],v);
		mnsz=mn(mnsz,sz[v]);
	}
	int l=mx(secmx,(firmx+mnsz+1)/2);
	int r=firmx-1;ans[x]=firmx;
	while(l<=r){
		int mid=l+r>>1;
		int szl=firmx-mid;
		int szr=mid-mnsz;
		int res=0;
		if(mxid==-1){
			//链上的 sz 需要 -sz[x]
			res+=S.query(1,1,n,mx(0,szl+sz[x]),mn(n,szr+sz[x]));
			//除去链上的部分和子树的部分进行查询
			res+=Q(1,dfn[x],szl,szr)+Q(dfn[x]+sz[x],n,szl,szr);
			res-=S.query(1,1,n,mx(0,szl),mn(n,szr)); 
		}
		else res=Q(dfn[mxid]+1,dfn[mxid]+sz[mxid]-1,mx(szl,1),mn(szr,n));
		if(res){ans[x]=mid;r=mid-1;}
		else l=mid+1;
	}
	return ;
} 

inline void dfs2(int x){
	S.update(1,1,n,sz[x],1);
	Solve(x);
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;dfs2(v); 
	}
	S.update(1,1,n,sz[x],-1);
	return ;
} 
int main()
{
	read(n);
	for(int i=1;i<=n;i++){
		read(ex);read(ey);
		fa[ey]=ex;
		if(ex) add(ex,ey);
		else rt=ey;
	}
	dfs1(rt); 
	for(int i=1;i<=n;i++) 
		root[i]=ins(root[i-1],1,n,sz[idfn[i]]);
	dfs2(rt);
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}