洛谷P3942将军令

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

　　题目传送门

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

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

#include<bits/stdc++.h>

#define N 100010

using namespace std;

int n,k,t,que[N],fa[N];

int head[N],dis[N],size;

struct Node{int to,next;}edge[N<<];

bool exity[N];

inline int read()

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';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[]=;que[]=;

  int h=,t=;

  while(h<t){

    h++;int x=que[h];

    for(int i=head[x];i!=-;i=edge[i].next){

      int y=edge[i].to;

      if(y==fa[x])continue;

      fa[y]=x;que[++t]=y;

    }

  }

}

void dfs(int u,int dep)

{

  exity[u]=true;dis[u]=dep;

  if(dep==)return ;

  for(int i=head[u];i!=-;i=edge[i].next){

    int y=edge[i].to;

    if(dis[y]<dis[u]-||!exity[y])

      dfs(y,dep-);

  }

}

void ready()

{

  memset(exity,false,sizeof(exity));

  memset(head,-,sizeof(head));

  n=read();k=read();t=read();

  for(int i=;i<n;i++){

    int x=read();int y=read();

    add(x,y);add(y,x);}

  bfs();

}

void work()

{

  memset(dis,,sizeof(dis));

  int ans=;

  for(int i=n;i>=;i--){

    int x=que[i];

    if(!exity[x]){

      ++ans;

      for(int j=k;j>;j--)x=fa[x];

      dfs(x,k);

    }

  }

  printf("%d",ans);

  return ;

}

int main()

{

  ready();

  work();

  return ;

}

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