题意
修改一条边意味着，删掉一条边，并加入一条新的边。
给出一棵树，对于每个点，求出使它变成重心的最小修改边数。
分析
先找到重心，对于不是重心的一个点 \(i\)， 有两种方法，一是将重心的前几个大的子树接在 \(i\) 下面（当然不包括 \(i\) 属于的子树），二是将重心和其余子树一起接到 \(i\) 下面，再不断割 重心的前几个大的子树 ,使得 重心 在以 \(i\) 为根的 size 小于等于 \(n/2\) 。为什么呢？源于重心的定义。这样可以先求出重心，在将子树 sort 一下，求前缀和，再二分需要割的子树数量，就是答案了。
\(code\)
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,tot,root,maxpart=1e9,cnt;
int Head[N],to[N<<1],Next[N<<1];
int size[N],c[N],sum[N],pos[N],vv[N];
struct node{
int id,val;
bool operator < (const node& A)const{return val>A.val;}
}son[N];
void add(int u,int v){
to[++tot]=v,Next[tot]=Head[u],Head[u]=tot;
}
void dfs1(int x,int fa){
size[x]=1;int maxn=0;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];if(y==fa) continue;
dfs1(y,x);size[x]+=size[y];
maxn=max(maxn,size[y]);
}
maxn=max(maxn,n-size[x]);
if(maxn<maxpart) maxpart=maxn,root=x;
}
void dfs(int x,int fa,int gp){
size[x]=1,c[x]=gp;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];if(y==fa) continue;
dfs(y,x,gp);size[x]+=size[y];
}
}
void dfs2(int x,int fa){
size[x]=1;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];if(y==fa) continue;
dfs(y,x,y);size[x]+=size[y];
son[++cnt].id=y,son[cnt].val=size[y];
}
}
int main(){
// freopen("diortnec.in","r",stdin);
// freopen("diortnec.out","w",stdout);
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs1(1,0);
dfs2(root,0);
sort(son+1,son+1+cnt);
for(int i=1;i<=cnt;++i) sum[i]=sum[i-1]+son[i].val,pos[son[i].id]=i,vv[son[i].id]=son[i].val;
for(int i=1;i<=n;++i){
if(i==root){printf("0\n");continue;}
int l=0,r=cnt,ans1=0,ans2=0;
while(l<=r){
int mid=(l+r)>>1;
int val=sum[mid],flag=0;
if(pos[c[i]]<=mid) val-=vv[c[i]],flag=1;
if(size[c[i]]+val>=(n+1)/2) ans1=mid-flag,r=mid-1;
else l=mid+1;
}
l=0,r=cnt;
while(l<=r){
int mid=(l+r)>>1;
int val=sum[mid],flag=0;
if(pos[c[i]]<=mid) val-=vv[c[i]],flag=1;
if(size[i]+val>=(n+1)/2) ans2=mid-flag,r=mid-1;
else l=mid+1;
}
write(min(ans1+1,ans2)),puts("");
}
// fclose(stdin);
// fclose(stdout);
return 0;
}