赛时只打了暴力。
Part1
我们考虑在什么情况下要放一个村民，我们设根节点的深度为 \(0\), 那么对于一个节点 \(u\) ,如果在其子树内有一个叶子结点 \(v\), 满足 \(dis_{u, v} \leqslant dep_u\), 那么只要在这个节点放一个村民，就可以把 \(u\) 节点堵住，原因显然。
我们想要让村民尽量少，那么就要让被堵住的节点尽量少，尽量靠上，这样一个村民的价值才能发挥到最大。设一个节点 \(u\) 到最近叶子的距离为 \(mnd_u\), 那我们要找的就是几棵最大的子树（子树根节点为 \(u\) ,其父节点为 \(fa\) ），满足 \(mnd_u \leqslant dep_u\) ,这个节点显然满足 \(mnd_u \leqslant dep_u\) ， \(mnd_{fa} > dep_{fa}\) , 答案就是这种节点的个数。
Part2
题目要求求出每个节点作为出发点时的答案，直接统计不好算，我们考虑转化。
对于一棵子树，设其节点个数为 \(size_u\), 设一个节点 \(i\) 的度数为 \(deg_i\), 那么必然有:
那我们设一个节点的权值 \(val_i\) 为 \((2-deg_i)\)， 那么对于任意一棵子树，子树内节点的权值和为 \(1\). 那么统计所有满足条件的点，其权值和即为答案，一个节点 \(v\) 对节点 \(u\) 有贡献， 当且仅当 \(dis_{u,v} \geqslant mnd_v\)。证明可以考虑，放村民的那个叶子结点 \(v\), 和这棵极大子树内的任意一个节点 \(u\) 的距离 一定不大于 \(u\) 和根节点的距离。这个可以画图理解一下。
Part3
现在把问题转化成了树上点对贡献问题， 可以使用点分治和树状数组解决。
具体的，设当前的分治中心为 \(root\) ,那么那么可以把条件改变一下，拆分成：
每次遍历整棵分治树，把节点 \(v\) 的权值放到下标为 \(mnd_v-dis_{v,root}\) 的位置，处理答案时，先删去一棵子树的信息，子树内的节点 \(u\) 查询 \(dis_{u,root}\)， 累加贡献。然后再把这棵子树的信息加上。重复这个过程。处理完整棵分治树后集体删去信息，再递归分治树就可以了（不要忘了计算分治中心的贡献）。
复杂度为 $\Theta(n\log^2 n) $。 可以通过。
Code
#include <iostream>
#include <cstdio>
#include <queue>
const int N=7e4+10;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
int n, cnt_edge;
struct edge {
int next, to;
}e[N<<1];
int head[N], du[N];
int mnd[N], val[N], ans[N];
void add_edge(int u,int v) {
e[++cnt_edge].to=v;
e[cnt_edge].next=head[u];
head[u]=cnt_edge;
du[v]++;
}
queue <int> q;
void BFS() {
for(int i=1;i<=n;i++) mnd[i]=n+1;
for(int i=1;i<=n;i++) {
if(du[i]==1) {
mnd[i]=0;
q.push(i);
}
}
while(!q.empty()) {
int now=q.front(); q.pop();
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(mnd[v] > mnd[now]+1) {
mnd[v]=mnd[now]+1;
q.push(v);
}
}
}
}
struct BIT {
int t[N<<1];
inline int lowbit(int x) {return x&(-x);}
inline void up_date(int pos,int val) {
while(pos<=n*2) {
t[pos]+=val;
pos+=lowbit(pos);
}
}
inline int query(int pos) {
int res=0;
while(pos) {
res+=t[pos];
pos-=lowbit(pos);
}
return res;
}
}B;
struct Point_Part {
int sum_root, root;
int maxp[N], dis[N], size[N];
bool vis[N];
void get_root(int now,int fa) {
size[now]=1, maxp[now]=0;
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(v==fa || vis[v]) continue;
get_root(v, now);
size[now]+=size[v];
maxp[now]=max(maxp[now], size[v]);
}
maxp[now]=max(maxp[now], sum_root-maxp[now]);
if(maxp[now]<maxp[root]) root=now;
}
void get_dis(int now,int fa) {
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(v==fa || vis[v]) continue;
dis[v]=dis[now]+1;
get_dis(v, now);
}
}
void change(int now,int fa,int type) {
int pos=mnd[now]-dis[now]+n;
B.up_date(pos, type*val[now]);
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(v==fa || vis[v]) continue;
change(v ,now ,type);
}
}
void calc(int now,int fa) {
int pos=dis[now]+n;
ans[now]+=B.query(pos);
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(v==fa || vis[v]) continue;
calc(v ,now);
}
}
void solve(int now) {
vis[now]=1, dis[now]=0;
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(vis[v]) continue;
dis[v]=dis[now]+1;
get_dis(v, now);
}
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(vis[v]) continue;
change(v, now, 1);
}
ans[now]+=B.query(n);
int pos=mnd[now]+n;
B.up_date(pos, val[now]);
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(vis[v]) continue;
change(v ,now, -1);
calc(v, now);
change(v, now ,1);
}
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(vis[v]) continue;
change(v, now, -1);
}
B.up_date(pos, -val[now]);
for(int i=head[now];i;i=e[i].next) {
int v=e[i].to;
if(vis[v]) continue;
sum_root=size[v], root=0;
get_root(v ,0);
solve(root);
}
}
void work() {
maxp[0]=n+1, sum_root=n;
get_root(1, 0);
solve(root);
}
}P;
int main() {
n=read();
for(int i=1;i<n;i++) {
int u=read(), v=read();
add_edge(u, v);
add_edge(v, u);
}
BFS();
for(int i=1;i<=n;i++) {
val[i]=2-du[i];
}
P.work();
for(int i=1;i<=n;i++) write(ans[i]);
return 0;
}