代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

const int MAXN = 51000;

struct Edge{
  int to,len;
  int nex;
}edge[MAXN*2];int fir[MAXN],ecnt = 2;

void addedge(int a,int b,int c){
  edge[ecnt] = (Edge){b,c,fir[a]};
  fir[a] = ecnt++;
}

int n,m;
int ANS,TAR;

void init(){
  scanf("%lld %lld",&n,&m);
  for(int i = 2;i<=n;i++){
    int a,b,c;
    scanf("%lld %lld %lld",&a,&b,&c);
    addedge(b,a,c),addedge(a,b,c);
  }
}


vector<int> S[MAXN];

bool cmp(int a,int b){
  return a > b;
}

pair<int,int> check2(int nown){
  sort(S[nown].begin(),S[nown].end(),cmp);
  int l = S[nown].size();
  if(l == 0)
    return make_pair(0,0);
  if(l == 1)
    return make_pair(0,S[nown][0]);
  if(S[nown][0] + S[nown][1] < TAR)
    return make_pair(0,S[nown][0]);
  // printf("%lld\n",nown);
  // for(unsigned i = 0;i<S[nown].size();i++){
  //   printf("%lld ",S[nown][i]);
  // }
  // printf("\n");
  int ans = 0;
  int notvis_max = 0,LL = 0,RR = l-1;
  while(true){
    if(LL > RR) break;
    while(LL < RR && S[nown][RR] + S[nown][LL] < TAR){
      notvis_max = S[nown][RR];
      RR--;
    }
    if(LL == RR){
      notvis_max = S[nown][LL];
      break;
    }
    ans++;
    LL++,RR--;
  }
  return make_pair(ans,notvis_max);
}

int dfs(int nown,int fa){
  for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
    int v = edge[nowe].to,len = edge[nowe].len;
    if(v == fa) continue;
    int t = dfs(v,nown) + len;
    if(t >= TAR){
      ANS++;
    }
    else{
      if(t != 0){
        //printf("nown:%lld push:%lld\n",nown,t);
        S[nown].push_back(t);
      }
    }
  }
  pair<int,int> pp = check2(nown);
  // printf("%lld: pp:%lld %lld\n",nown,pp.first,pp.second);
  ANS += pp.first;
  return pp.second;
}

bool check(int x){
  // printf("check:%lld-------------\n",x);
  for(int i = 1;i<=n;i++)
    S[i].clear();
  ANS = 0;TAR = x;
  int t = dfs(1,0);
  if(t >= TAR) ANS++; 
  // printf("ANS:%lld\n",ANS);
  return ANS >= m;
}

void solve(){
  int L = 1,R = 0x3f3f3f3f;
  while(L!=R){
    int mid = ((L+R-1)>>1) + 1;
    if(check(mid))
      L = mid;
    else
      R = mid-1;
  }
  printf("%lld\n",L);
}

signed main(){
  init();
  solve();
  return 0;
}

评测结果