题目概述

给出一棵 $n$ 个节点的树，求每个点成为与其他点距离和最小点最少需要删除并加上的边数 $k$（新加边之后依然是一棵树）。

解题报告

我根本发现不了性质.jpg。可以证明，到其他点距离和最小的点与重心等价（如果一个点不是重心，那么往重心那边移动一下，肯定会得到更小的距离和）。

那么问题转化为使一个点 $x$ 变成重心（等价于所有子树的大小均 $\le\lfloor{n\over 2}\rfloor$ ，设 $lim=\lfloor{n\over 2}\rfloor$ ）需要删除并加上多少边，根据贪心，我们一定是选出最大的大小 $>lim$ 的子树，将其接到 $x$ 的子树上。

于是可以DP，将 $x$ 当成根建树，从下往上删除 $>lim$ 的最大的子树直到每个点的大小都满足 $\le lim$ 。

但是这道题要把每个点都问一遍……于是要进行修正工作，树形DP修正工作的套路就是考虑某个子树强制不选，然后累加上面过来的贡献，这样就可以算出每个子树了。

由于不能和一次DP一样暴力删除，所以我们记录一下排序过后的前缀和，在前缀和上二分就可以快速求出至少需要删除的个数，讨论一下前缀和有没有跨过当前待求的子树，分两种情况二分就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=1000000;

int n,lim,sum[maxn+5],ans[maxn+5];pair<int,int> f[maxn+5],g[maxn+5],F[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b) {return a>b;}
void Dfs(int x,int pre=0,int m=0){
    for (int j=(f[x].sc=1,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) Dfs(son[j],x),f[x].fr+=f[son[j]].fr,f[x].sc+=f[son[j]].sc;
    if (f[x].sc<=lim) return;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) F[++m]=mp(f[son[j]].sc,son[j]);
    sort(F+1,F+1+m,cmp);for (int i=1;i<=m&&f[x].sc>lim;i++) f[x].sc-=F[i].fr,f[x].fr++;
}
inline int Find(int L,int R,int val){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        sum[mid]>=val?R=mid-1:L=mid+1;return L;
}
void Solve(int x,int pre=0,int m=0){
    ans[x]=g[x].fr;for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) ans[x]+=f[son[j]].fr;
    for (int j=(F[++m]=mp(g[x].sc,x),g[x].sc++,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) F[++m]=mp(f[son[j]].sc,son[j]),g[x].fr+=f[son[j]].fr,g[x].sc+=f[son[j]].sc;
    sort(F+1,F+1+m,cmp);for (int i=1;i<=m;i++) sum[i]=sum[i-1]+F[i].fr;
    for (int i=1,u;i<=m;i++){
        if ((u=F[i].sc)==x) continue;int si=g[x].sc-f[u].sc,num;
        if (si-sum[i-1]<=lim) num=Find(0,i-1,si-lim),si-=sum[num];
        else num=Find(i+1,m,si+f[u].sc-lim),si-=sum[num]-f[u].sc,num--;
        g[u].fr=g[x].fr-f[u].fr+num;g[u].sc=si;
    }for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Solve(son[j],x);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);lim=n>>1;for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    Dfs(1);Solve(1);for (int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}