救民于水火

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;

void read(int &x){
	int r=0;
	char s;
	s=getchar();
	while(s>'9' ||s<'0') s=getchar();
	while(s>='0'&&s<='9'){
		r=r*10+s-'0';
		s=getchar();
	}
	x=r;
}

int n,m;
int head[2*maxn],to[2*maxn],nex[2*maxn],val[2*maxn],num=0;
void add(int x,int y,int z){
	to[++num]=y;
	nex[num]=head[x];
	head[x]=num;
	val[num]=z;
}
int ans=0;
int dfs(int x,int f,int k){
	multiset<int> s;//可以自动排序，并且课一用lower bound upper bound
	int all=0;
	for(int i=head[x];i;i=nex[i]){
		int u=to[i];
		if(u==f) continue;
		all=dfs(u,x,k)+val[i];
		if(all>=k) ans++;
		else s.insert(all);//要不然就存进去
	} 
	int len=0;
	while(!s.empty()){
		int tmp = *s.begin();//这里返回的是指针
		s.erase(s.begin()); 
		multiset<int> ::iterator it=s.lower_bound(k-tmp);//找到可以和他配对的边
		if(it==s.end()) len=max(len,tmp);//返回最长的没有匹配的边 
		else s.erase(it) ,ans++;
	}
	return len;
}


bool check(int mid){
	ans=0;
	dfs(1,0,mid);
	if(ans>=m) return true;
	else return false;
}

int main(){
	read(n);
	read(m);
	int up=0;
	for(int i=1;i<n;i++){
		int a,b,c;
		read(a);read(b);read(c);
		add(a,b,c);
		add(b,a,c);
		up+=c;
	}
	int l=0,r=up/m,mid;
	
	while(l<r){
		mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<"\n";
	
	return 0;
}