5941번: Cow Calisthenics

https://www.acmicpc.net/problem/5941


$O(n{\lg n}^2)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int v, s, d[100001];
vector<int> adj[100001];
int f(int h, int p, int l) {
    int c = 0, i;
    vector<int> v;
    for (auto it : adj[h]) if (it^p) {
        c += f(it, h, l);
        v.push_back(d[it] + 1);
    }
    if (v.empty()) return 0;
    sort(v.begin(), v.end());
    for (i = v.size(); --i&&v[i - 1] + v[i] > l;) c++;
    d[h] = v[i] % (l + 1);
    return c + (v[i] > l);
}
int main() {
    scanf("%d%d", &v, &s);
    for (int i = 0, x, y; i < v - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int low = 0, up = v - 1, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        f(1, 0, mid) <= s ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", low);
    return 0;
}