代码

#include<bits/stdc++.h>
using namespace std;
int cnt,fst[50005],nxt[100005],to[100005],w[100005];
int n,m,l=2147400000,r,mid,ans,f[50005],g[50005];
multiset <int> s;
multiset <int>::iterator it;
void AddEdge(int u,int v,int c)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
    w[cnt]=c;
}
void Dfs(int u,int faz)
{
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz) continue;
        Dfs(v,u);
        f[u]+=f[v];
    }
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz) continue;
        s.insert(g[v]+w[i]);
    }
    while(!s.empty())
    {
        int now=*s.rbegin();
        if(now>=mid)
        {
            it=s.find(now);
            f[u]++;
            s.erase(it);
        }
        else break;
    }
    while(!s.empty())
    {
        int now=*s.begin();
        s.erase(s.begin());
        it=s.lower_bound(mid-now);
        if(it==s.end()) g[u]=now;
        else
        {
            f[u]++;
            s.erase(it);
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        AddEdge(x,y,z);
        AddEdge(y,x,z);
        l=min(l,z);
        r+=z;
    }
    while(l<=r)
    {
        mid=l+r>>1;
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        Dfs(1,0);
        if(f[1]>=m)
        {
            ans=max(ans,mid);
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d",ans-1);
    return 0;
}

评测结果