点分治 hot tea。
首先考虑什么样的点能够对以 \(u\) 为根的答案产生 \(1\) 的贡献。我们考虑以 \(u\) 为根对整棵树进行一遍 DFS。那么对于一个点 \(v\)，我们记其 \(mn_v\) 为其子树内距离其最近的叶子，\(dep_v\) 为 \(u\) 到 \(v\) 的距离，那么如果 \(mn_v\ge dep_v\)，那么对于任何一个 \(v\) 子树内的叶子 \(w\)，如果 Bessie 选择从 \(w\) 逃出且我们在距离 \(v\) 最近的叶子处放上一个看守者，那么在 \(v\) 处的看守者必然能够在 Bessie 到达 \(w\) 之前把 Bessie 截住。并且根据贪心的原理，只有当如果 \(v\) 的父亲 \(fa_v\) 不符合 \(mn_{fa_v}\ge dep_{fa_v}\) 时我们才会选择在距离 \(v\) 最近的叶子，并且这样的点必须被选，否则 \(v\) 子树内的点就堵不住了。因此一个点 \(v\) 产生条件的必要条件是 \(mn_v\ge dep_v\land mn_{fa_v}<dep_{fa_v}\)。那这是否充分了呢？或者说是否会存在某个叶子，满足两个产生贡献的点都选到这个点。答案是否定的，因为如果存在两个点 \(v_1,v_2\)，满足距离它们最近的叶子相同，并且 \(mn_{v_1}\ge dep_{v_1},mn_{v_2}\ge dep_{v_2}\) 均成立，那么必然有它们的 LCA 也符合要求。因此对于一个 \(u\)，满足条件的 \(v\) 的个数就是
\[\sum\limits_{v}[mn_v\ge\text{dis}(v,u)][mn_{fa_v}<\text{dis}(fa_v,u)]
\]
注意到这里涉及两个维度，如果硬要上个点分治那需要三位偏序，非常麻烦。不过注意到对于一个点，如果其满足第一个限制，那么它的子树也满足这个限制。那么怎样让每个子树的贡献都只算一次呢？考虑一个大小为 \(x\) 的子树 \(S\)，由于该子树中深度最浅的节点上面还连了条边，因此该节点中所有点的度 \(d_v\) 之和等于 \(2x-1\)，移个项可得 \(\sum\limits_{v\in S}2-d_v=1\)，因此上式等价于
\[\sum\limits_{v}(2-d_v)·[mn_v\ge\text{dis}(v,u)]
\]
这东西就一脸可以点分治的样子了，考虑对于一个 \(u\) 以及一个与其不在一个分治中心儿子子树内的点 \(v\)，那么记 \(dep_u\) 为 \(u\) 到分治中心的距离，那么限制可转化为 \(mn_v\ge dep_u+dep_v\)，移个项可得 \(mn_v-dep_v\ge dep_u\)，BIT 维护即可，时间复杂度 \(n\log^2n\)。
const int MAXN=7e4;
const int INF=0x3f3f3f3f;
int n,deg[MAXN+5],hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int mx[MAXN+5],cent=0,siz[MAXN+5];bool vis[MAXN+5];
int mndep[MAXN+5],mnout[MAXN+5],mn[MAXN+5];
void dfs1(int x,int f){
mndep[x]=(deg[x]==1)?0:INF;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;
dfs1(y,x);chkmin(mndep[x],mndep[y]+1);
}
}
void dfs2(int x,int f){
multiset<int> st;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];
if(y==f) st.insert(mnout[x]);
else st.insert(mndep[y]+1);
}
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;
if(deg[x]==1) mnout[y]=1;
else{
st.erase(st.find(mndep[y]+1));
mnout[y]=(*st.begin())+1;
st.insert(mndep[y]+1);
} dfs2(y,x);
}
}
void findcent(int x,int f,int tot){
siz[x]=1;mx[x]=0;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f||vis[y]) continue;
findcent(y,x,tot);siz[x]+=siz[y];chkmax(mx[x],siz[y]);
} chkmax(mx[x],tot-siz[x]);
if(mx[x]<mx[cent]) cent=x;
}
int dep[MAXN+5];
void getdep(int x,int f){
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(vis[y]||y==f) continue;
dep[y]=dep[x]+1;getdep(y,x);
}
}
ll t[MAXN*2+5],res[MAXN+5];
void add(int x,int v){x+=n+1;for(int i=x;i<=(n<<1|1);i+=(i&(-i))) t[i]+=v;}
ll query(int x){x+=n+1;ll ret=0;for(int i=x;i;i&=(i-1)) ret+=t[i];return ret;}
vector<int> pt;
void getpts(int x,int f){
pt.pb(x);
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(vis[y]||y==f) continue;
getpts(y,x);
}
}
void divcent(int x){
//printf("divcent %d\n",x);
vis[x]=1;dep[x]=0;vector<int> tot;tot.pb(x);
add(mn[x]-dep[x],2-deg[x]);stack<int> stk;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(vis[y]) continue;
dep[y]=1;getdep(y,x);stk.push(y);
pt.clear();getpts(y,x);
for(int p:pt) res[p]+=query(dep[p]);
for(int p:pt) add(mn[p]-dep[p],2-deg[p]),tot.pb(p);
} for(int y:tot) add(mn[y]-dep[y],deg[y]-2);
tot.clear();
while(!stk.empty()){
int y=stk.top();stk.pop();
pt.clear();getpts(y,x);
for(int p:pt) res[p]+=query(dep[p]);
for(int p:pt) add(mn[p]-dep[p],2-deg[p]),tot.pb(p);
} res[x]+=query(dep[x]);
for(int y:tot) add(mn[y]-dep[y],deg[y]-2);
tot.clear();
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(vis[y]) continue;
cent=0;findcent(y,x,siz[y]);divcent(cent);
}
}
int main(){
//freopen("P4183_7.in","r",stdin);
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
adde(u,v);adde(v,u);deg[u]++;deg[v]++;
} dfs1(1,0);mnout[1]=INF;dfs2(1,0);
for(int i=1;i<=n;i++) mn[i]=min(mndep[i],mnout[i]);
//for(int i=1;i<=n;i++) printf("%d %d %d\n",mn[i],mndep[i],mnout[i]);
mx[0]=INF;findcent(1,0,n);divcent(cent);
for(int i=1;i<=n;i++) printf("%lld\n",res[i]);
return 0;
}
