EOJ Monthly 2020.9 Sponsored by TuSimple B. 健康监测计划

EOJ Monthly 2020.9 Sponsored by TuSimple B. 健康监测计划

题目链接

规律题~
对于 $k$ 为偶数的时候，就是取 $\frac{k}{2}$ 次叶子(一次是指取当前图中的所有叶子结点，且每取一次叶子结点都要删去)，当 $k$ 为奇数的时候，多取一个结点，AC代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,k,u,v,ans=0,d[N],h[N];
vector<int>G[N];
queue<int>q;
int main(){scanf("%d%d",&n,&k);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);d[u]++,d[v]++;G[u].push_back(v),G[v].push_back(u);}if(k==0||k==1){printf("%d",k);return 0;}for(int i=1;i<=n;i++) if(d[i]==1) q.push(i),h[i]=1;while(!q.empty()){u=q.front();q.pop();ans++;for(auto v:G[u]){h[v]=h[u]+1;if(h[v]<=k/2&&--d[v]==1) q.push(v);}}printf("%d",min(n,ans+k%2));return 0;
}