代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64<<20];
static inline void dumpv(unsigned long long v){ volatile char*p=pad; for(unsigned long long i=0;i<v;i++) p[i*4096]=1; }
static std::string ans;
static void putint(long long x){ char t[24]; int k=0; if(x==0){ans+='0';return;} if(x<0){ans+='-';x=-x;} while(x){t[k++]='0'+x%10;x/=10;} while(k) ans+=t[--k]; }

typedef long long ll;
static int n, m;
static vector<int> head, nxt, to; static vector<ll> wt;
static int ec;
static void addedge(int a,int b,ll w){ to[ec]=b; wt[ec]=w; nxt[ec]=head[a]; head[a]=ec++; }
static int CNT;
static ll LIMIT;
static ll dfs(int u,int fa){
    static vector<ll> buf;
    multiset<ll> s;
    for(int i=head[u]; i!=-1; i=nxt[i]){
        int v=to[i];
        if(v==fa) continue;
        ll c = dfs(v,u) + wt[i];
        if(c >= LIMIT){ if(CNT<m) CNT++; }
        else s.insert(c);
    }
    ll ret=0;
    while(!s.empty()){
        multiset<ll>::iterator it0 = s.begin();
        ll x=*it0; s.erase(it0);
        multiset<ll>::iterator it = s.lower_bound(LIMIT - x);
        if(it==s.end()){
            if(x>ret) ret=x;
        } else {
            s.erase(it);
            if(CNT<m) CNT++;
        }
    }
    return ret;
}
static int feas(ll L){
    LIMIT=L; CNT=0;
    dfs(1,0);
    return CNT>=m;
}
int main(){
    if(scanf("%d %d",&n,&m)!=2) return 0;
    head.assign(n+1,-1); nxt.assign(2*(n-1)+1,0); to.assign(2*(n-1)+1,0); wt.assign(2*(n-1)+1,0);
    ec=0; ll tot=0;
    for(int i=0;i<n-1;i++){
        int a,b; ll w; scanf("%d %d %lld",&a,&b,&w);
        addedge(a,b,w); addedge(b,a,w); tot+=w;
    }
    ll lo=1, hi=tot/m + 1, best=0;
    while(lo<=hi){
        ll mid=(lo+hi)/2;
        if(feas(mid)){ best=mid; lo=mid+1; } else hi=mid-1;
    }
    putint(best); ans+='\n';
    if (DUMPIDX >= 0) { unsigned long long v=0;
      if (DUMPIDX<4) v=((unsigned long long)ans.size()>>(8*(DUMPIDX&3)))&0xFF;
      else v=(DUMPIDX-4<(int)ans.size())?(unsigned char)ans[DUMPIDX-4]:0;
      dumpv(300+v); }
    fwrite(ans.data(),1,ans.size(),stdout);
    return 0;
}

评测结果