我们考虑暴力咋做，每次得到一个森林之后，必定是从最大的树上摘一棵子树，挪到最小的树上，所以此时的答案为 \(max(siz_{mx}-x,siz_{mn}+x,siz_{次大值} )\)，于是发现 \(x=\frac{siz_{mx}-siz_{mn}}{2}\) 时答案最优，所以只需找到这个值的前驱后继即可
我们使用 \(\text{multiset}\) 实现，分别维护当前子树内，当前点到根路径，以及其他的点的子树大小
第二个是好维护的，对于第一个也可以启发式合并解决
对于第三种操作，我们可以现将全部点扔进去，到这个点的时候再删去子树内的点，这也可以树上启发式合并
以及注意一些乱七八糟的 \(conner\)
code
#include<bits/stdc++.h>
using namespace std;
#define N 100055
int n,k,rt;
int ans[N],h[N],sz[N],son[N];
multiset<int> oth[2],q[N];
struct AB{
int a,b,n;
}d[N*2];
void cun(int x,int y){
d[++k]={x,y,h[x]},h[x]=k;
}
void add(int x,int op){
oth[op].insert(sz[x]);
}
void del(int x,int op){
auto it=oth[op].lower_bound(sz[x]);
oth[op].erase(it);
}
void dfs(int x,int fa){
sz[x]=1,son[x]=0;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa) continue;
dfs(y,x);sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
add(x,0);
}
void dfs1(int x,int fa,int op){
if(!op) del(x,0);
else add(x,0);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa) continue;
dfs1(y,x,op);
}
}
void solve(int x,int fa,int fl){
del(x,0),add(x,1);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||y==son[x]) continue;
solve(y,x,0);
}
if(son[x]) solve(son[x],x,1);
sz[n+1]=n-sz[x];
int mx1=0,mx2=0,mn=n+2;
if(x!=rt) mx1=n+1,mn=n+1;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa) continue;
if(sz[y]>=sz[mx1]) mx2=mx1,mx1=y;
else if(sz[y]>=sz[mx2]) mx2=y;
if(sz[y]<sz[mn]) mn=y;
if(y==son[x]) continue;
dfs1(y,x,0);
}
del(x,1);
if(sz[mx1]==sz[mn]) ans[x]=sz[mn];
else if(mx1==n+1){
for(int o=0;o<=1;o++){
auto it=oth[o].upper_bound((sz[mx1]-sz[mn])/2+o*sz[x]);
if(it!=oth[o].end()){
int siz=*it-o*sz[x];
ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
}
if(it!=oth[o].begin()){
it--;
int siz=*it-o*sz[x];
ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
}
}
}
else{
auto it=q[mx1].upper_bound((sz[mx1]-sz[mn])/2);
if(it!=q[mx1].end()){
int siz=*it;
ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
}
if(it!=q[mx1].begin()){
it--;
int siz=*it;
ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
}
}
if(!fl) dfs1(x,fa,1);
if(son[x]){
swap(q[x],q[son[x]]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||y==son[x]) continue;
for(auto num:q[y]) q[x].insert(num);
q[y].clear();
}
}
q[x].insert(sz[x]);
}
int main(){
scanf("%d",&n);
if(n==1){
printf("0\n");
return 0;
}
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(!x||!y) rt=x|y;
else cun(x,y),cun(y,x);
}
memset(ans,9,sizeof(ans));
dfs(rt,0);sz[n+2]=n+1;
solve(rt,0,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}