代码

#include<cstdio>
#include<set>
using namespace std;
const int N=5e4+50;
int fir[N],las[N<<1],to[N<<1],ds[N<<1],cnt;
inline void add_edge(int u,int v,int a){
    to[++cnt]=v;las[cnt]=fir[u];fir[u]=cnt;ds[cnt]=a;
    to[++cnt]=u;las[cnt]=fir[v];fir[v]=cnt;ds[cnt]=a;
}
inline int min(int u,int v){return u<v?u:v;}
inline int max(int u,int v){return u>v?u:v;}
int n,m,x,y,z,l,r,mid,Ans;
multiset<int>s[N];
typedef multiset<int>::iterator IT;
int dfs(int u,int v){
    int qwq=0,qvq=0;
    IT it;
    for(int i=fir[u];i;i=las[i])
    if(to[i]!=v){
        qvq=dfs(to[i],u)+ds[i];
        if(qvq>=mid)++Ans;
        else s[u].insert(qvq);
    }
    while(s[u].size()){
        qvq=*s[u].begin();
        s[u].erase(s[u].begin());
        it=s[u].lower_bound(mid-qvq);
        if(it!=s[u].end()){
            Ans++;
            s[u].erase(it);
        }else qwq=qvq;
    }
//	if(s[u].size()){
//		if(*s[u].begin()>=mid)Ans++;
//		else qwq=*s[u].begin();
//		s[u].clear();
//	}
    return qwq;
}
bool ok(){
    Ans=0;
    dfs(1,0);
    return Ans>=m;
}
int main(){
    scanf("%d%d",&n,&m);
    l=2e9;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        l=min(l,z);
        r+=z;
    }
    r/=m;
    while(l<r){
        mid=l+r+1>>1;
        if(ok())l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}

评测结果