Description：

给一棵树，去掉其中的 $m$ 条边，最小化直径的最大值。

$1\leqslant n\leqslant 10^5$

Solution：

双最值问题想二分，设当前二分的值为 $k$ ，那么就要求不能有长度超过 $k$ 的链，然后就可以树形 $DP$ ，类似 $DP$ 求直径的做法， $f[i]$ 表示从点 $i$ 到叶子的最长长度，如果在某一个点有两条链合并起来长度超过 $k$ ，那就必须截断一条，具体的处理办法是在每个点把所有儿子节点的 $f[i]+1$ 拿出来排序，然后用双指针扫一个从大开始一个从小开始扫描，如果不合法了就把大的剪掉，合法小的就走一步。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int cnt = 0;

int f[MAXN];

bool v[MAXN];

int s[MAXN],top = 0;

void dp(int k,int l)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to,l);

	}

	top = 0;

	s[++top] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		s[++top] = f[e[i].to] + 1;

	}

	sort(s + 1,s + 1 + top);

	int i,j;

	for(i = 1,j = top;i < j;)

	{

		if(s[i] + s[j] > l)

		{

			++cnt;

			--j;

		}

		else ++i;

	}

	f[k] = s[i];

	v[k] = false;

	return;

}

bool check(int k)

{

	cnt = 0;

	dp(1,k);

	return (cnt <= m);

}

int main()

{

	n = rd();m = rd();

	for(int i = 1;i < n;++i)add(rd(),rd());

	int l = 0,r = n,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	cout << l << endl;

	return 0;

}