P5536 [XR-3] Core Cities

Country X has $n$ cities and $n - 1$ roads of length $1$. Each road connects two cities, and any two cities can reach each other through some roads. Obviously, the cities and roads form a tree. The king of Country X decides to designate $k$ cities as the core cities of Country X, and the remaining cities are non-core cities. These $k$ core cities must satisfy the following two conditions: 1. These $k$ cities can reach each other pairwise via roads without passing through any non-core city. 2. Define the distance from a non-core city to the $k$ core cities as the minimum value among its distances to the $k$ core cities. To measure traffic conditions, the king invented the traffic congestion level, which is the maximum value among the distances from all non-core cities to the core cities. The problem is: how should we choose the core cities to minimize the traffic congestion level? Output the minimum possible traffic congestion level that satisfies the conditions.

The first line contains $2$ positive integers $n, k$. The next $n - 1$ lines each contain $2$ positive integers $u, v$, meaning there is a road of length $1$ between city $u$ and city $v$. **Constraints:** - $1 \le k < n \le 10 ^ 5$. - $1 \le u, v \le n, u \ne v$, and it is guaranteed that the cities and roads form a tree.

One line with one integer, representing the minimum traffic congestion level that satisfies the conditions.

[Sample Explanation] Designate cities $1, 2, 5$ as the $3$ core cities. Then the distances from the other $3$ non-core cities $3, 4, 6$ to the core cities are all $1$, so the answer is $1$. Translated by ChatGPT 5