啦啦啦，又是五月天的歌～～～～～～

　　

　　那么来分析下题目;给定你一棵树，告诉你一支队伍能管辖的范围，求能覆盖整棵树的最少队伍数。

　　嘛，如果不会做，第一个想到的肯定是暴搜嘛，但是代码打起来肯定也非常麻烦。正解其实和最短路有类似的地方，也需要用到树状结构里常用的father数组;首先给定你一棵树以后，以一号结点为根，一遍广搜确定每个结点的father，也就是无根树转有根树;然后按照队列入队的逆序开始遍历，如果该点没有被控制，那么就从这个结点的第K个祖先开始深搜，这样才能控制尽可能多的点（想不通的话可以自己画棵树试试看），在深搜过程中也要注意更新dis值，不然就会挂的很惨了！如果不懂，结合代码分析应该很好理解：

#include
     
      #define N 100010using namespace std;int n,k,t,que[N],fa[N];int head[N],dis[N],size;struct Node{
   int to,next;}edge[N<<1];bool exity[N];inline int read(){  char ch=getchar();int num=0;bool flag=false;  while(ch<'0'||ch>'9'){
   if(ch=='-')flag=true;ch=getchar();}  while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}  return flag?-num:num;}void add(int x,int y){  edge[++size].to=y;  edge[size].next=head[x];  head[x]=size;}void bfs(){  fa[1]=1;que[1]=1;  int h=0,t=1;  while(h
      
       =1;i--){    int x=que[i];    if(!exity[x]){      ++ans;      for(int j=k;j>0;j--)x=fa[x];      dfs(x,k);    }  }  printf("%d",ans);  return ;}int main(){  ready();  work();  return 0;}
      
     

就是这样了，这题就这么过去了～～～