#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;
int n,m,lim,cnt;
struct Node{
	int fa,mson;
}nod[50004];
struct Edge{
	int v,w;
	Edge(int _v,int _w):
		v(_v),w(_w)
	{}
	Edge(){}
};
struct cmp{
	bool operator()(const Edge &x,const Edge &y){
		return x.w<y.w;
	}
};
std::basic_string<Edge> G[50004];
void dfs(int fa,int x){
	nod[x].fa=fa;
	for(auto e:G[x]){
		if(e.v==fa)continue;
		dfs(x,e.v);
	}
}

void dp(int x){
	std::multiset<int>s;
	for(auto e:G[x]){
		if(e.v==nod[x].fa)continue;
		dp(e.v);
		s.insert(e.w+nod[e.v].mson);
	}
	//cerr<<x<<endl;
	auto iter=s.end();
	if(!s.empty()){
		iter--;
	}
//	cerr<<"QAQsize "<<s.size()<<endl;
	while(!s.empty()&&*iter>=lim){
//		cerr<<"iter "<<*iter<<endl;
		s.erase(iter);
		cnt++;
		iter--;
	}
	while(s.size()>1){
		int it=*s.begin();
		s.erase(s.begin());
		auto tmp=s.lower_bound(lim-it);
		if(tmp!=s.end())s.erase(tmp),cnt++;
//		cerr<<"size "<<s.size()<<endl;
	}	
	if(!s.empty()){
		nod[x].mson=(*--s.end());
	}else nod[x].mson=0;
	return;
}
bool check(int x){
	lim=x,cnt=0;
	dp(1);
//	cerr<<"lim "<<lim<<" cnt "<<cnt<<" m "<<m<<endl;
	return cnt>=m; 
}
int main(){
	#ifdef LOCAL
		freopen("test.in","r",stdin);
		freopen("test.err","w",stderr);
		freopen("test.out","w",stdout);
	#endif
	std::ios::sync_with_stdio(false);
	cerr.tie(nullptr),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	int l=0,r=1;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		r+=w;
		G[u]+=Edge(v,w);
		G[v]+=Edge(u,w);
	}
	dfs(0,1);
	//cerr<<"outdfs"<<endl;
	while(l<r-1){
		int mid=(l+r)>>1;
		if(check(mid)){
			l=mid;
		}else {
			r=mid;
		}
//		cerr<<mid<<endl;
	}
	cout<<l<<endl;
	return 0;
}

代码如上

提交记录