题目传送门
【题目大意】
这个题面有点中二啊hhhh
总结一下就是给出了一棵$n$个节点的树，然后在一个节点驻扎小队就可以控制树上所有距离它不超过$k$的节点，求最少需要驻扎多少个小队就可以控制整棵树。
【思路分析】
首先有一个非常显然的结论，如果把小队驻扎在叶子节点显然是比驻扎在非叶子节点要不优的，所以我们可以考虑将所有点按照深度从大到小排序。
每次取出一个当前深度最大的点，如果这个点已经被覆盖过了，那就跳过，否则找到这个点的第$k$级祖先，在此驻扎小队，$ans++$，并覆盖掉所有距此的距离不大于$k$的点。
最后输出$ans$即为答案。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 #define to(i) e[i].to 16 #define E(i,x) for(rg int i=head[x];i;i=e[i].next) 17 using namespace std; 18 int fr(){ 19 int w=0,q=1; 20 char ch=g(); 21 while(ch<'0'||ch>'9'){ 22 if(ch=='-') q=-1; 23 ch=g(); 24 } 25 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 26 return w*q; 27 } 28 const int N=1e5+2; 29 int n,k,ed=0,head[N],f[N],dep[N],ans; 30 bool vis[N]; 31 struct edge{ 32 int next,to; 33 }e[N<<1]; 34 struct Tree{ 35 int id,d; 36 }t; 37 priority_queue<Tree> q; 38 il bool operator < (Tree x,Tree y) {return x.d<y.d;}//重载运算符 39 il void build(rg int u,rg int v){ 40 e[++ed].next=head[u]; 41 e[ed].to=v;head[u]=ed; 42 return; 43 } 44 il void tree(rg int x,rg int fa){ 45 E(i,x){ 46 if(to(i)==fa) continue; 47 dep[to(i)]=dep[x]+1;f[to(i)]=x; 48 tree(to(i),x); 49 } 50 return; 51 } 52 il int find(rg int x){ 53 rg int kk=1; 54 while(kk<=k&&x!=f[x]){ 55 kk++; 56 x=f[x]; 57 } 58 return x; 59 } 60 il void work(rg int fa,rg int x,rg int kk){ 61 vis[x]=1; 62 if(kk==k) return; 63 E(i,x) if(to(i)!=fa) work(x,to(i),kk+1); 64 return; 65 } 66 int main(){ 67 //freopen("","r",stdin); 68 //freopen("","w",stdout); 69 n=fr();k=fr();fr(); 70 go(i,1,n-1){ 71 rg int u=fr(),v=fr(); 72 build(u,v);build(v,u); 73 } 74 f[1]=1;dep[1]=1;tree(1,1); 75 go(i,1,n) t=(Tree){i,dep[i]},q.push(t); 76 while(!q.empty()){ 77 t=q.top();q.pop(); 78 if(vis[t.id]) continue; 79 ans++; 80 rg int fa=find(t.id); 81 work(fa,fa,0); 82 } 83 pf("%d\n",ans); 84 return 0; 85 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11549398.html
