啦啦啦，又是五月天的歌～～～～～～
那么来分析下题目;给定你一棵树，告诉你一支队伍能管辖的范围，求能覆盖整棵树的最少队伍数。
嘛，如果不会做，第一个想到的肯定是暴搜嘛，但是代码打起来肯定也非常麻烦。正解其实和最短路有类似的地方，也需要用到树状结构里常用的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<<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<t){ h++;int x=que[h]; for(int i=head[x];i!=-1;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==0)return ; for(int i=head[u];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]<dis[u]-1||!exity[y]) dfs(y,dep-1); } } void ready() { memset(exity,false,sizeof(exity)); memset(head,-1,sizeof(head)); n=read();k=read();t=read(); for(int i=1;i<n;i++){ int x=read();int y=read(); add(x,y);add(y,x);} bfs(); } void work() { memset(dis,0,sizeof(dis)); int ans=0; for(int i=n;i>=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; }
就是这样了，这题就这么过去了～～～