-
注意到“最大值最小”，考虑二分最大直径。
-
对于当前直径，树形dp + 贪心的封锁。
-
f[u]：以 u 为根的子树，叶节点到 u 的最大距离 +1。 -
在树形dp时维护
mx，与f[u]组成直径。 -
复杂度 \(\mathcal{O}(n\log n)\)。
View Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, s, head[N], idx, f[N], cnt, ans;
struct Edge{int v, nxt;} e[N << 1];
inline void add(int u, int v)
{
e[++idx] = {v, head[u]};
head[u] = idx;
}
inline void dfs(int u, int fa, int res)
{
int mx = 0;
for(int i = head[u];~i;i = e[i].nxt)
{
int v = e[i].v;
if(v == fa) continue;
dfs(v, u, res);
if(f[v] + mx > res)
{
++cnt;
mx = min(mx, f[v]);
}
else mx = max(mx, f[v]);
}
f[u] = mx + 1;
}
inline bool check(int mid)
{
cnt = 0;
dfs(1, -1, mid);
return cnt <= s;
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &s);
for(int i = 1, u, v;i < n;++i)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
int l = 0, r = n - 1;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid))
{
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}