rt

AC:https://www.luogu.com.cn/record/117205684

RE:https://www.luogu.com.cn/record/117206014

code

#include <bits/stdc++.h>
#define N 500005
using namespace std;
int n,m,cnt,bmp;
int d[N],vis[N];
struct apple{
	int v,w;
};
apple ur;
vector <apple> g[N];
multiset <int> q[N];
multiset<int>::iterator fr;
multiset<int>::iterator dr;

inline int read(){
	register int s=0,w=1;
	char ch;
	while (ch<'0'||ch>'9'){
		if (ch=='-'){
			w=w*(-1);
		}
		ch=getchar();
	}
	while ('0'<=ch&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}


inline void write(int x){
	register int cnt=0;
	char f[405];
    if (x<0){
    	putchar('-');
    	x=-x;
	}
	if (x==0){
		putchar('0');
	}
	while (x){
		f[cnt++]=x%10+'0';
		x=x/10;
	}
	while (cnt){
		putchar(f[--cnt]);
	}
}

int check(int u,int fa,int k){
	//cout<<u<<" "<<fa<<" "<<k<<endl;
	int val,up=0;
	q[u].clear();
	for (int i=0;i<g[u].size();i++){
		ur=g[u][i];
		int v=ur.v,w=ur.w;
		if (v==fa){
			continue; 
		}
		val=w+check(v,u,k);
		if (val>=k){
			cnt++;
		}else{
			q[u].insert(val); 
		}
	}
	while (!q[u].empty()){
		fr=q[u].begin();
		dr=q[u].lower_bound(k-*q[u].begin());
		if (fr==dr){
			dr++;
		}
		q[u].erase(fr);
		if (dr==q[u].end()){
			up=max(up,*fr);
		}else{
			q[u].erase(dr);
			cnt++;
		}
	}
	return up;
}

int dp(int u){
	vis[u]=1;
	for (int i=0;i<g[u].size();i++){
		ur=g[u][i];
		int v=ur.v,w=ur.w;
		if (vis[v]){
			continue;
		}
		dp(v); 
		bmp=max(bmp,d[u]+d[v]+w);
		d[u]=max(d[u],d[v]+w); 
	}
}

int main (){
	int i,u,v,w,l=1,r=0,mid,ans,p;
	n=read(),m=read();
	for (i=1;i<n;i++){
		u=read(),v=read(),w=read(); 
		ur.v=v,ur.w=w;
		g[u].push_back(ur);
		ur.v=u;
		g[v].push_back(ur);
	}
	dp(1);
	r=bmp;
	//cout<<bmp<<endl; 
	//cout<<"init"<<endl;
	while (l<=r){
		int mid=l+r>>1;
		cnt=0;
		p=check(1,0,mid);
		//cout<<"&&"<<l<<" "<<r<<" "<<cnt<<endl; 
		if (cnt>=m){
			ans=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	write(ans);
	return 0;
}