4009번: 순찰

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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, k, d[MXN + 1], l[MXN + 1], r;
vector<int> adj[MXN + 1];
void f(int h, int p) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) if (it^p) {
        f(it, h);
        l[h] = max(l[h], l[it]);
        m2 = max(m2, d[it] + 1);
        if (m1 < m2) swap(m1, m2);
    }
    if (m2) l[h] = max(l[h], m1 + m2);
    d[h] = m1;
}
void g(int h, int p, int pd, int pl) {
    int l1 = pl, l2 = 0;
    pair<int, int> c[4] = { { pd,p }, };
    for (auto it : adj[h]) if (it^p) {
        if (c[3] < make_pair(d[it] + 1, it)) {
            c[3] = { d[it] + 1,it };
            for (int i = 3; i; i--) if (c[i] > c[i - 1]) swap(c[i], c[i - 1]);
        }
        l2 = max(l2, l[it]);
        if (l1 < l2) swap(l1, l2);
    }
    r = max({ r,pd + d[h],l[h] });
    if (k == 2) {
        r = max(r, pl + l[h]);
        if (c[3].first) r = max(r, c[0].first + c[1].first + c[2].first + c[3].first);
    }
    for (auto it : adj[h]) if (it^p) {
        int td1 = 0, td2 = -1e9, tl = l[it] ^ l1 ? l1 : l2;
        for (int i = 0; i < 4; i++) if (c[i].second^it&&c[i].second) {
            if (!td1) td1 = c[i].first;
            else if (td2 < 0) td2 = c[i].first;
        }
        g(it, h, td1 + 1, max(td1 + td2, tl));
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    g(1, 0, 0, 0);
    printf("%d", n * 2 + k - r - 2);
    return 0;
}