X 国有 n 座城市，n−1 条长度为 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国国王决定将 k 座城市钦定为 X 国的核心城市，这 k 座城市需满足以下两个条件：

这 k 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
定义某个非核心城市与这 k 座核心城市的距离为，这座城市与 k 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

题解：
先找出树直径的中心root，以它为根节点，然后dfs去二分深度找答案

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
int head[maxn], tot, father[maxn];
struct Edge {
    int u, v, next;
} edge[maxn];

void init() {
    memset(head, -1, sizeof(head));
    tot = 1;
}

void add(int u, int v) {
    edge[++tot].u = u;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}

int root, dp[maxn], depth[maxn], cnt[maxn];
int mx;

void dfs(int u, int fa) {
    int mx1 = 0, mx2 = 0;
    father[u] = fa; dp[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        dfs(to, u);
        dp[u] = max(dp[u], dp[to] + 1);
        if (dp[to] > mx1) {
            mx2 = mx1;
            mx1 = dp[to];
        } else if (dp[to] > mx2) {
            mx2 = dp[to];
        }
    }
    if (mx1 + mx2 > mx) {
        root = u;
        mx = mx1 + mx2;
    }
}

void getRoot(int u, int fa) {
    root = u;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        if (dp[to] > mx / 2) {
            getRoot(to, u);
        }
    }
}

void init_dp(int u, int fa) {
    cnt[u] = 1; depth[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        init_dp(to, u);
        depth[u] = max(depth[u], depth[to] + 1);
        cnt[u] += cnt[to];
    }
}

int n, k, u, v;

int check(int u, int fa, int x) {
    if (depth[u] <= x) return cnt[u];
    int res = 0;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        res += check(to, u, x);
    }
    return res;
}

int main() {
    //freopen("in.in", "r", stdin);
    init();
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    getRoot(root, father[root]);
    init_dp(root, 0);
    int l = 1, r = depth[root];
    int ans = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (n - check(root, 0, mid) <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}