代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn=500010;
const ll INF=2147483647;
struct edge{
	ll to,val;
}e[maxn];
ll n,m,head[maxn],nxt[maxn],tot,x,y,z,l,r,ans[maxn],len[maxn],fa[maxn],cnt;
bool vis[maxn];
multiset<ll>s;

multiset<ll>::iterator it;
void add_edge(ll x,ll y,ll z){
	nxt[++tot] = head[x];
	e[tot].to = y;
	e[tot].val = z;
	head[x] = tot;
}
void dfs(ll x,ll sum){
	vis[x] = 1;
	for(int i = head[x]; i;i = nxt[i]){
		ll tem = e[i].to;
		if(!vis[tem]){
			fa[tem] = x;
			dfs(tem,sum);
		}
	}
	s.clear();
	for(int i = head[x]; i;i = nxt[i]){
		ll tem = e[i].to;
		if(fa[tem] != x)continue;
		if(e[i].val + len[tem] >= sum)ans[x]++;
		else s.insert(e[i].val + len[tem]);
	}
	ll maxx = 0;
	while(!s.empty()){
		if(s.size() == 1){
			maxx = max(maxx,*s.begin());

			break;

		}
		it = s.lower_bound(sum - *s.begin());

		if(it == s.begin() && s.count(*it) == 1)it++;
		if(it == s.end()){
			maxx = max(maxx,*s.begin());

			s.erase(s.find(*s.begin()));

		}
		else{
			ans[x]++;
			s.erase(s.find(*it));
			s.erase(s.find(*s.begin()));

		}
	}
	len[x] = maxx;
	cnt += ans[x];
	return;
}
bool check(ll x){
	cnt = 0;
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
	dfs(1,x);
	return (cnt >= m) ? true : false;
}
int main()
{

	ios::sync_with_stdio(false);

	cin>>n>>m;
	for(int i = 1;i < n;i++){
		cin>>x>>y>>z;
		add_edge(x,y,z);

		add_edge(y,x,z);

	}
	l = 1;
	r = INF;
	while(l < r - 1){
		ll mid = (l + r)>>1;
		if(check(mid)){
			l = mid;
		}
		else r = mid;
	}
	cout<<l;
	return 0;
}

评测结果