代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define M 50010
using namespace std;
int n,m,num,mid,sum,ans,l,r,maxn,p;
int head[M],vis[M];
struct point{int next,to,dis;}e[M<<1];
struct node{int id,v;};
vector<node>S[M];
bool operator < (node a1,node a2){return a1.v<a2.v;}
void add(int from,int to,int dis)
{
    e[++num].next=head[from];
    e[num].to=to;
    e[num].dis=dis;
    head[from]=num;
}
int dfs(int x,int fa)
{
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            int l=dfs(e[i].to,x)+e[i].dis,to=e[i].to;
            S[x].push_back((node){to,l});
        }
    int G=S[x].size();
    sort(S[x].begin(),S[x].end());
    for(int i=G-1;i>=0;i--) 
    {
        if(S[x][i].v>=mid) sum++,vis[S[x][i].id]=true;
        else break;
    }
    for(int i=0;i<G;i++)
    {
        int u=S[x][i].id,l=S[x][i].v;
        if(vis[u]) continue;
        for(int j=i+1;j<G;j++)
        {
            if(vis[S[x][j].id]) continue;
            if(l+S[x][j].v<mid) continue;
            vis[u]=vis[S[x][j].id]=true;
            sum++;
            break;
        }
    }
    for(int i=G-1;i>=0;i--)
        if(!vis[S[x][i].id])
            return S[x][i].v;
    return 0;
}
void DFS(int x,int fa,int now)
{
    if(now>=maxn) maxn=now,p=x;
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
            DFS(e[i].to,x,now+e[i].dis);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
        r+=c;
    }
    if(n>=1000&&m==1)
    {
        DFS(1,0,0);
        maxn=0;
        DFS(p,0,0);
        cout<<maxn<<endl;
        return 0;
    }
    r/=m;
    while(l<=r)
    {
        for(int i=1;i<=n;i++) 
            S[i].clear();
        memset(vis,false,sizeof(vis));
        mid=(l+r)/2;
        sum=0,dfs(1,1);
        if(sum<m) r=mid-1;
        else ans=mid,l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

评测结果