题目大意：有一只狐狸从给定的S点开始逃跑(出发)，向叶节点移动以逃离这棵树，叶节点可能出现农民去抓捕狐狸，当农民和狐狸出现在同一个节点的时候，狐狸会被抓住，农民和狐狸移动速度相同，求抓捕狐狸所需要的最少农民数
显然，当 u 节点的子树内存在一叶节点 i 满足deep[i]-deep[u]<=deep[u]时，说明 u 的子树能被守住
即农民从 i 移动到 u 所需要的时间小于等于狐狸从出发点移动到 u 的时间
第一遍dfs预处理出每个节点的深度dep，以及每个节点的子树内深度最小的叶节点的深度mindep(代码中简化为mi)
第二遍dfs求答案，只要某个节点能被其子树内某个叶节点守住，那么它子树内其它节点就不用考虑了，return 1
但并不能从S点直接开始第二个dfs，而是从S点直接连接的所有节点开始，因为狐狸和农民移动速度一样，如果按之前的方法，狐狸可能会往相反方向跑，导致农民无法追上狐狸
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define N 100005 5 #define inf 0x3f3f3f3f 6 #define maxn 1000010 7 using namespace std; 8 //re 9 10 int n,S,cte; 11 int head[N],dep[N],mi[N],inc[N]; 12 struct Edge{int to,nxt;}edge[N*2]; 13 void ae(int u,int v){ 14 cte++;edge[cte].to=v,inc[v]++; 15 edge[cte].nxt=head[u],head[u]=cte; 16 } 17 void dfs1(int u,int fa) 18 { 19 if(inc[u]==1) {mi[u]=dep[u];return;} 20 for(int j=head[u];j;j=edge[j].nxt){ 21 int v=edge[j].to; 22 if(v==fa) continue; 23 dep[v]=dep[u]+1; 24 dfs1(v,u); 25 mi[u]=min(mi[u],mi[v]); 26 } 27 } 28 int dfs2(int u,int fa) 29 { 30 int ans=0; 31 if(mi[u]-dep[u]<=dep[u]) 32 return 1; 33 for(int j=head[u];j;j=edge[j].nxt){ 34 int v=edge[j].to; 35 if(v==fa) continue; 36 ans+=dfs2(v,u); 37 } 38 return ans; 39 } 40 41 int main() 42 { 43 scanf("%d%d",&n,&S); 44 int x,y,ans=0; 45 for(int i=1;i<n;i++) 46 scanf("%d%d",&x,&y),ae(x,y),ae(y,x); 47 memset(mi,0x3f,sizeof(mi)); 48 dfs1(S,-1); 49 for(int j=head[S];j;j=edge[j].nxt){ 50 int v=edge[j].to; 51 ans+=dfs2(v,S); 52 }printf("%d ",ans); 53 return 0; 54 }