玄武观wa on 78(菊花) +17 18 19 20

#include<bits/stdc++.h>
using namespace std;
long long n,m,ff[500015],num[500015],ji[500015],ssm;
struct sss{
    long long b,l;
}p;
vector<sss>poi[500015];
inline void dfs(long long now,long long f){
    ff[now]=f;
    for(int i=0;i<poi[now].size();i++){
        if(poi[now][i].b==f)continue;
        num[poi[now][i].b]=poi[now][i].l;
        dfs(poi[now][i].b,now);
    }
}
long long fa[500015];
inline long long gt(long long x){
    if(fa[x]==x)return x;
    return fa[x]=gt(fa[x]);
}
long long jj[500015];

inline void ck(long long x,long long now){
    if(poi[now].size()==1 && now!=1){
        
        if(num[now]>=x){
            ssm++;
            ji[now]=0;
            
        }
        else ji[now]=num[now];
        return;
    }
    
    long long top=0;
    
    long long tmp[poi[now].size()+10];
    
    for(int i=0;i<poi[now].size();i++){
        if(x==1 && now==1)exit(1);
        if(ff[now]==poi[now][i].b)continue;
        
        ck(x,poi[now][i].b);
        if(ji[poi[now][i].b]!=0){
            tmp[++top]=ji[poi[now][i].b];
            fa[top]=top;
            jj[top]=0;
        }
        
    }
    for(int i=1;i<=top+10;i++)jj[i]=0,fa[i]=i;
    for(int i=top+1;i<=top+10;i++)fa[i]=0;
    fa[0]=0;
    sort(tmp+1,tmp+top+1);
    for(int i=1;i<=top;i++){
        if(jj[top]==1)continue;
        long long l=i+1,r=top,ans=-1;
        while(l<=r){
            long long mid=(l+r)/2;
            if(tmp[mid]+tmp[i]>=x){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }        
        if(ans!=-1 && gt(ans)<=top && gt(ans)>=1){
            ssm++;
            jj[gt(ans)]=1;
            jj[i]=1;
            fa[gt(ans)]=gt(gt(ans)+1);
            
            fa[gt(i)]=gt(gt(i)+1);
            
        }
    }
    for(int i=top;i>=1;i--){
        if(jj[i]==0){
            ji[now]=num[now]+tmp[i];
            if(ji[now]>=x){
                ssm++;
                ji[now]=0;
            }
            return;
        }
    }   
    ji[now]=num[now];
    if(ji[now]>=x){
        ssm++;
        ji[now]=0;
    }
    return;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<n;i++){
        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        poi[a].push_back((sss){b,c});
        poi[b].push_back((sss){a,c});
    }
    

    dfs(1,1);
    
long long l=1,r=1000000000000,ans=-1;
   while(l<=r){
        long long mid=(l+r)/2;
        memset(ji,0,sizeof(ji));
        ssm=0;
        ck(mid,1);
        if(ssm>=m){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }   
    printf("%lld",ans);
}