健康监测计划

链接：https://acm.ecnu.edu.cn/contest/317/problem/B/
思路：
按k我们来考虑k=0，那么肯定一个都不放，k=1，那么显然只能放一个，k=2呢？所有叶子结点都放，先去想k=4，那就是把叶子结点都去了，然后新的树中的叶子结点。k=3呢？就是k=4中，新选的点中随便取一个。这样一直把外圈缩进k/2次，所有的叶子结点就都是答案，那么如何判断k/2次呢，记录个深度，如果深度<=k/2并且它是叶子结点就算是要去的点。用queue把叶子结点放进来，并且每个叶子结点更新它对连的点，时间复杂度O（n）

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+7;
queue<int> q;
vector<int> g[maxn];
int d[maxn];
int dep[maxn];
struct Node{
    int x, d;
    bool operator < (const Node n1) const{
        return d < n1.d;
    }
};

int main()
{
    int n, k;
    cin>>n >> k;
    for(int i = 1; i <= n-1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);g[v].push_back(u);
        d[u]++;d[v]++;
    }
    if(k == 0){
        cout << 0 << endl; return 0;
    }
    else if(k == 1) {
        cout << 1 << endl; return 0;
    }
    for(int i = 1; i <= n; i++) {
        if(d[i] == 1) {
            q.push(i);
            dep[i] = 1;
        }
    }
    int ans = 0;
    while(!q.empty()){
        int tmp = q.front(); q.pop();
        ans++;
        for(auto to : g[tmp]){
            dep[to] = max(dep[to], dep[tmp]+1); 
            if(dep[to] <= k/2 && --d[to] == 1){
                q.push(to);
            }
        }
    }
    cout << min(n, ans+k%2);

}