Ryan_<

题意：

给定一棵树，要求删去K条边，使得分离出的各个子树中，最大的直径最小。

n<=10^5

分析：

其实思路还是蛮简单清晰的。

像这种最大值最小或者最小值最大的问题，二分答案是个不错的选择。二分答案之后问题就变成了对于当前这个树，最少需要删掉几条边才能使各个子树最大的半径都小于或等于某个值，如果删掉的边的数量比S小或者和S相等，那么就有可能使各个子树最大的直径等于一个更小的值。

至于最少删几条边才能使各个子树的最大的直径都小于或等于某个值，可以在dfs的时候利用贪心的思想解决。

记f[x]为满足二分的答案p限制的、从x出发的最长路（不需要记录子树直径！），cnt为至少需要割掉的边。dfs回溯时从底向上贪心求cnt,并更新f[]：

如果当前节点出发的最长路与次长路长度之和<=二分值p，则该节点为根的子树一定满足要求；否则要将当前最长路对应节点与当前节点割开，累加答案。

时间复杂度O(n*log^2n) 每次排序有一个log.

int n,K,cnt,num;
int f[N],tmp[N];
void dfs(int x,int ff,int p)
{
	f[x]=0;
	R(i,x){
		int y=e[i].go;
		if(y==ff) continue;
		dfs(y,x,p);
	}//回溯时自底向上处理 
	num=0;tmp[0]=0;//注意边界 
	R(i,x){
		int y=e[i].go;
		if(y==ff) continue;
		tmp[++num]=f[y]+1; 
	}
	sort(tmp+1,tmp+num+1);
	while(num&&tmp[num]+tmp[num-1]>p) num--,cnt++;
	f[x]=tmp[num];
}
bool check(int p)
{
	cnt=0;dfs(1,0,p);
	if(cnt<=K) return true;
	else return false;
}
int main()
{
//	freopen("exercise.in","r",stdin);
	n=read();K=read();
	F(i,1,n-1){
		int x=read(),y=read();
		addedge(x,y);
	}
	int l=1,r=n-1;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}