Dona Minhoca.cpp

#include<bits/stdc++.h>
using namespace std;
const int inf = (int) 1e9 + 10;
const int maxn = 3e5+10;

int n, k;
vector<int> g[maxn];

int qtd_radar;
pair<int,int> dfs(int u, int r, int pai) {
    int rad = inf;
    int des = 0;

    for(auto v : g[u]) {
        if(v == pai) continue;
        pair<int,int> aux = dfs(v,r,u);
        int rad_v = aux.first;
        int des_v = aux.second;
        des = max(des,des_v+1);
        rad = min(rad,rad_v+1);
    }
    if(des+rad <= r) {
        des = -1;
    }
    if(des == r) {
        qtd_radar++;
        des = -1;
        rad = 0;
    }
    return make_pair(rad,des);
}

bool check(int r) {
    qtd_radar = 0;
    auto aux = dfs(1,r,0);
    if(aux.second >= 0) qtd_radar++;
    return qtd_radar <= k;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    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);
    }

    int l = 1;
    int r = n;
    int ans = n;
    while(l <= r) {
        int mid = (l+r)/2;
        if(check(mid)) {
            ans = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    cout << ans << endl;
}