题目大意：

给你一棵树，让你把它剖成 $m$ 条链，问其中最短的链最长是多少。

Solution：

看到最小的最大这种问题，我们可以想到二分答案，那么问题就变成了给你一棵树，将其剖成 $m$ 条链，是其中最短的链大于 $mid$。
对于这个问题，我们可以使用 DFS 来解决。我们先开一个数组 $b$，$b_u$ 就表示以 $u$ 为根的子树中，所有以 $u$ 为起点的链中长度没有达到 $mid$ 的链或者不能与另一条没有达到 $mid$ 的链拼在一起来超过 $mid$ 的链中最长的那条链的长度。

Part 1：遍历子树

遍历 $u$ 时，先枚举它的所有儿子，设儿子的编号为 $v$，到 $u$ 的边的长度为 $w$，我们先 DFS(v)，然后如果 $b_v+w\ge mid$，就将 $tot$ 加 1，否则就将其存入数组 $a$ 中。

Part 2：合并链

我们将 $a$ 数组从小到大排序，然后从小到大枚举，对于每个 $i$，如果能找到一个 $j$，使 $a_i+a_j\ge mid$，且 $j$ 最小，那么就将 $tot$ 加 1，然后把 $i$ 和 $j$ 标记一下，这一部分可以用二分做。然后如果 $j$ 已经被标记过了，就把 $j$ 往后跳，直到 $j$ 没有被标记，如果跳出去了就不管它。注意不能想当然的用双指针，因为可能开始已经把一些点跳过了，但它们并没有被标记，导致后面可能有些链本来能匹配的，却没有匹配到。

Part 3：上传 $b$ 数组

我们从剩余的没有标记的链中取个最大值，传进 $b_u$ 中，然后这题就做完了，时间复杂度 $O(n\log^2n)$。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,tot,cnt,f[50001],bz[50001],a[50001],b[50001],sum,mid;
struct edge{int to,w;};
vector<edge>G[50001];
inline void init(int u){
	for(auto[v,w]:G[u]){
		if(f[u]!=v){
			f[v]=u;
			init(v);
		}
	}
}void dfs(int u){
	for(auto[v,w]:G[u])if(f[u]!=v)dfs(v);
	cnt=0;
	for(auto[v,w]:G[u]){
		if(f[u]!=v){
			if(b[v]+w>=mid)++tot;
			else a[++cnt]=b[v]+w;
		}
	}sort(a+1,a+cnt+1),fill(bz+1,bz+cnt+1,0);
	for(int i=1;i<cnt;i++){
		if(bz[i])continue;
		int j=lower_bound(a+i+1,a+cnt+1,mid-a[i])-a;
		if(j!=cnt+1){
			while(bz[j]&&j<cnt)++j;
			if(!bz[j]&&a[i]+a[j]>=mid)bz[i]=bz[j]=1,++tot;
		}
	}b[u]=0;
	for(int i=1;i<=cnt;i++)if(!bz[i])b[u]=a[i];
}bool check(){
	tot=0,dfs(1);
	return tot>=m;
}signed main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<n;++i){
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
		sum+=w;
	}init(1);
	int l=0,r=sum,ans=0;
	while(l<=r){
		mid=(l+r)/2;
		if(check())ans=mid,l=mid+1;
		else r=mid-1;
	}cout<<ans;
}