题目
首先有结论：
一个点为关键点（可以由该点的子树中出发，正好在该点拦截住奶牛），当且仅当 \(g_u \le dist(root,u) , g_{fa} > dist(root,fa)\),其中 \(g_u\) 表示
距离 \(u\) 最近的叶节点。
那么 \(18pts\) 就是 \(O(n^2)\) 的暴力了
void dfs(int u,int fa){
dis[u] = (G.d[u] == 1 ? 0 : inf);
for(int i = G.head[u];i;i = G[i].nxt)if(G[i].v != fa){
int v = G[i].v; dfs(v,u); dis[u] = min(dis[v] + 1,dis[u]);
}
}
int redfs(int u,int fa,int now){
if(dis[u] <= now)return 1;
int sum = 0; for(int i = G.head[u];i;i = G[i].nxt)if(G[i].v != fa)sum += redfs(G[i].v,u,now+1);
return sum;
}
for(int i = 1;i<=n;++i){
if(G.d[i] == 1){ puts("1"); continue; }
dfs(i,0)，printf("%d\n",redfs(i,0,0));
}
复杂度降不下来在于每次都要枚举 \(root\)。
观察结论中的条件，发现 \(g\) 是与根无关的，这与点分治的无根思想相吻合。
观察答案的统计。由于对答案产生贡献的是一棵棵子树，思考规模大小为 \(n\) 的子树有性质： $ ∑ d_i = (n \cdot 2) - 1\(，考虑到我们要避免`子树`这一概念的影响，应当将统计贡献转化到点上（我们并不在意子树是如何分配的）。那么对于一棵子树就有：\) ∑ (2 - d_i) = 1$。这是一个重要的构造。这呼应了符合根节点为关键点的子树的性质：子树内所有点都满足 \(g_i \le dist(root,i)\)。
从点分治的思考方向出发，又结合点分治可用于解决点对问题，我们可以得到：
\[ans_u = ∑_{i=1}^{n} [dist(u,i) \ge g_i](2-d_i) \]这里的 \(dist(u,i)\) 便是点对。思考点分治的具体解决方式。
对于 \(dist(u,i)\)，利用当前重心，有 \(dist(u,i) = dep_i + dep_u\)，进而自然地移项：
\[dep_u + dep_i \ge g_i \]\[dep_u \ge g_i - dep_i \]现在问题具有的特性，自然用数据结构维护。这里用的是权值树状数组。
CODE
#include<cstdio>
#include<algorithm>
#define for_edge for(int i = G.head[u],v = G[i].v;i;i = G[i].nxt,v = G[i].v)
const int N = 7e4 + 10,inf = 0x3f3f3f3f;
int n,g[N],dep[N],siz[N],mx[N],Tsiz,root,ans[N];
bool vis[N];
struct Graph{
int head[N],etot,d[N];
struct node{ int nxt,v; }edge[N<<1];
void add(int u,int v){
edge[++etot] = {head[u],v}; ++d[v];
head[u] = etot;
}
node & operator [](const int &i){ return edge[i]; }
}G;
void dfs(int u,int fa){//自下而上更新 g
g[u] = inf;
if(G.d[u] == 1)g[u] = 0;
for_edge{
if(v == fa)continue;
dfs(v,u);
g[u] = std::min(g[v] + 1,g[u]);
}
}
void redfs(int u,int fa){// 自上而下更新 g
for_edge{
if(v == fa)continue;
g[v] = std::min(g[v],g[u] + 1);
redfs(v,u);
}
}
void getroot(int u,int fa){
siz[u] = 1, mx[u] = 0;
for_edge{
if(v == fa || vis[v])continue;
getroot(v,u);
siz[u] += siz[v];
mx[u] = std::max(mx[u],siz[v]);
}
mx[u] = std::max(mx[u],Tsiz-siz[u]);
if(mx[u] < mx[root])root = u;
}
struct Bit{
#define lowbit(a) (a&(-a))
int c[N<<1];
void add(int x,int v){ for(register int i = x;i <= n*2;i += lowbit(i))c[i] += v; }
int query(int x){ int res = 0;for(register int i = x;i;i -= lowbit(i))res += c[i]; return res; }
#undef lowbit
}tr;
int st[N],top;
void init(int u,int fa){// 预处理当前子树的节点，每个节点到当前重心的深度
st[++top] = u;
for_edge{
if(v == fa || vis[v])continue;
dep[v] = dep[u] + 1;
init(v,u);
}
}
void cal(int u,int val,int op){// 统计答案
top = 0, dep[u] = val, init(u,0);
for(int i = 1;i<=top;++i)
tr.add(n + g[st[i]] - dep[st[i]],2 - G.d[st[i]]);
for(int i = 1;i<=top;++i)
ans[st[i]] += op * tr.query(dep[st[i]] + n);
for(int i = 1;i<=top;++i)
tr.add(n + g[st[i]] - dep[st[i]],G.d[st[i]] - 2);
}
void solve(int u){
cal(u,0,1); vis[u] = 1;
for_edge{
if(vis[v])continue;
cal(v,1,-1);// 去掉会重复统计的贡献(容斥)
Tsiz = siz[v], root = 0, getroot(v,0), solve(root);
}
}
int main(){
read(n);
for(int i = 1,u,v;i<n;++i)
read(u),read(v),G.add(u,v),G.add(v,u);
dfs(1,0), redfs(1,0);
mx[(root = 0)] = inf, Tsiz = n, getroot(1,0), solve(root);
for(int i = 1;i<=n;++i)write(G.d[i] == 1 ? 1 : ans[i]),putchar('\n');
return 0;
}