带有小 trick 的点分治。
建议先做完 弱化版 再看。
假如奶牛在 \(u\)，那么所需的最少农夫数为 \(\sum\limits_{v\in son(u)}[dis(u,v)\ge g_v][dis(u,fa_v)<g_{fa_v}]\)。
其中 \(dis(u,v)\) 为 \(u,v\) 在树上的距离，\(g_u\) 为 \(u\) 到离它最近的出入口的距离（BFS 预处理），\(fa_u\) 为 \(u\) 的父亲。
复杂度 \(O(n^2)\)。
由于 \(dis(u,fa_v)<g_{fa_v}\) 限制的存在，不好优化。
但通过人类智慧我们发现，对于 \(u\) 这棵子树，\(\sum\limits_{v\in son(u)}in_v=2n-1\)。其中 \(in_u\) 为 \(u\) 的度数，\(n\) 为子树大小，\(v\) 可以为 \(u\)。
将式子变换一下得：\(1=\sum\limits_{v\in son(u)}(2-in_v)\)。
这样原式就可以去掉后面的限制，变为 \(\sum\limits_{v\in son(u)}[dis(u,v)\le g_v](2-in_v)\)。
接下来点分治的操作和 这道题 很像，可以看一眼。
具体来说，对于分治重心 \(rt\) 中的两个点 \(u,v\)，当前仅当 \(g_u\le d_u+d_v\) 时，\(v\) 会对 \(u\) 产生贡献。其中 \(d_u\) 为 \(dis(u,rt)\)。这其实就是个点对问题。
所以我们可以以 \(g_u-d_u\) 为下标建一棵树状数组，每次访问前缀和即可。由于下标可能为负，所以需要整体平移一下。
复杂度 \(O(n\log^2 n)\)。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=7e4+5;
int n,g[N],vis[N],f[N],siz[N],d[N],c[N*2],in[N],tot,ans[N],t[N],cnt,rt;
queue<int>q;
vector<int>adj[N];
int lbt(int x){return x&(-x);}
void update(int i,int k){for(;i<=2*n;i+=lbt(i))c[i]+=k;}
int getsum(int i){int res=0;for(;i;i-=lbt(i))res+=c[i];return res;}
void dfs(int u,int lst){
siz[u]=1;f[u]=0;
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i];if(v==lst||vis[v])continue;
dfs(v,u);siz[u]+=siz[v];f[u]=max(f[u],siz[v]);
}
f[u]=max(f[u],tot-siz[u]);
if(f[u]<f[rt])rt=u;
}
void getdis(int u,int lst){
t[++cnt]=u;
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i];if(v==lst||vis[v])continue;
d[v]=d[u]+1;getdis(v,u);
}
}
void getans(int u,int len,int op){
d[u]=len;cnt=0;getdis(u,0);
for(int i=1;i<=cnt;++i)update(g[t[i]]-d[t[i]]+n,2-in[t[i]]);
for(int i=1;i<=cnt;++i){
update(g[t[i]]-d[t[i]]+n,in[t[i]]-2);
ans[t[i]]+=op*getsum(d[t[i]]+n);
update(g[t[i]]-d[t[i]]+n,2-in[t[i]]);
}
for(int i=1;i<=cnt;++i)update(g[t[i]]-d[t[i]]+n,in[t[i]]-2);
}
void solve(int u){
getans(u,0,1);vis[u]=1;
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i];if(vis[v])continue;
getans(v,1,-1);
rt=0;tot=siz[v];dfs(v,u);solve(rt);
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v;cin>>u>>v;
adj[u].push_back(v);adj[v].push_back(u);++in[u];++in[v];
}
for(int i=1;i<=n;++i)if(in[i]==1)q.push(i),vis[i]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i];if(vis[v])continue;
vis[v]=1;g[v]=g[u]+1;q.push(v);
}
}
for(int i=1;i<=n;++i)vis[i]=0;
f[0]=1e9;tot=n;dfs(1,0);solve(rt);
for(int i=1;i<=n;++i)cout<<ans[i]<<endl;
return 0;
}