题面
贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有N个结点的树，结点分别编号为 1,2,…,N 。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。抓捕过程中，农民们与贝茜均知道对方在哪个结点。
请问：对于结点 i((1leq ileq N))，如果开始时贝茜在该结点，最少有多少农民，她才会被抓住。
分析
先考虑问题的简化版，对于给定的起点s求出答案
设dist(x,y)表示x,y两点之间的距离
我们发现，对于某一个节点x,若$dist(s,x) geq min {dist(x,u) } $ 其中u为x的子树中的叶子节点，那么从x走到s的时
候就会被抓住.$min {dist(x,u) } $可以通过一次BFS预处理出来
显然奶牛越早被抓住更好，从节点s出发DFS，只要当前节点x满足上述条件，则ans++,并不访问x子树中的节点。因为如果在x点被抓住了，它就不会到比x深度更大的节点去了
这样的复杂度显然是(O(n^2))
有一个玄学优化，可以通过此题，方法如下
1.DP一遍求出每个点到最近的叶子节点的距离dp[x]
2.DFS，把链缩成一条边，因为可以发现不管在链的哪里拦截都是一样的
3.每次暴力，当dp[x]<=dist(x,root)的时候ans++,return
可以证明把链缩掉之后是(O(nsqrt{n}))的
由于没有链，我们可以把模型简化为一个满k叉树(k>1)，每次暴力DFS，显然DFS的深度不超过树的深度的1/2，即(O(log_kn))
访问的子树大小为
显然当k=2最大，为(2sqrt{n}-1),
所以总时间复杂度为(O(nsqrt{n})),与分块相同,且常数远小于点分治
代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 100005
#define INF 0x3f3f3f3f
using namespace std;
inline void qread(int &x){
x=0;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
}
inline void qprint(int x){
if(x==0){
putchar('0');
return;
}else{
if(x>=10) qprint(x/10);
putchar(x%10+'0');
}
}
int n,k;
struct edge{
int from;
int to;
int next;
int nfrom;
int nto;
int len;
}E[maxn<<1];
int head[maxn];
int deg[maxn];
int sz=1;
void add_edge(int u,int v){
deg[u]++;
deg[v]++;
sz++;
E[sz].from=u;
E[sz].to=v;
E[sz].next=head[u];
head[u]=sz;
}
int dp[maxn];//表示离x最近的叶子节点到x的距离
//不能从一个根开始DFS，因为此时根不定，
//到一个点最近的叶子节点不一定在DFS时的子树里，而可能在它上方
void bfs(){
queue<int>q;
for(int i=1;i<=n;i++){
if(deg[i]<=1){
q.push(i);
dp[i]=0;
}else dp[i]=INF;
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(dp[y]==INF){
dp[y]=min(dp[y],dp[x]+1);
q.push(y);
}
}
}
}
int s,t,d;
void dfs2(int x,int fa,int deep){
if(fa!=0&°[x]!=2){
s=x;
t=fa;
d=deep;
return;
}
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(y!=fa){
dfs2(y,x,deep+1);
E[i].nto=s;
E[i].nfrom=t;
E[i].len=d-deep;
}
}
}
int ans=0;
void dfs3(int x,int fa,int deep){
if(deep>=dp[x]){
ans++;
return;
}
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(y!=fa){
dfs3(E[i].nto,E[i].nfrom,deep+E[i].len);
}
}
}
int main(){
int u,v;
qread(n);
for(int i=1;i<n;i++){
qread(u);
qread(v);
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;i++) deg[i]/=2;
bfs();
for(int i=1;i<=n;i++){
if(deg[i]!=2) dfs2(i,0,0);
}
for(int i=1;i<=n;i++){
ans=0;
dfs3(i,0,0);
qprint(ans);
putchar('
');
}
}