代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#define mp make_pair
using namespace std;
const int N=80010;
int n,m,tot,Next[N*2],head[N],tree[N*2],val[N*2],top,Stack[N],V[N],P,f[N][2],A[N];
bool vis[N],FLAG;
set<pair<int,int> >S;
void add(int x,int y,int z)
{
    tot++;
    Next[tot]=head[x];
    head[x]=tot;
    tree[tot]=y;
    val[tot]=z;
}
void dfs(int u,int fa)
{
    int lasttop=top;
    for (int i=head[u];i;i=Next[i])
    {
        int v=tree[i];
        if (v==fa) continue;
        Stack[++top]=v;V[top]=val[i];
        dfs(v,u);
        if (FLAG) return;
    }
    int ans=0,cnt=0;
    for (int i=lasttop+1;i<=top;i++)
    {
        if (f[Stack[i]][0]+V[i]>=P) ans++;
            else A[++cnt]=f[Stack[i]][0]+V[i];
        ans+=f[Stack[i]][1];
    }
    sort(A+1,A+cnt+1);
    for (int i=1;i<=cnt;i++)
    {
        vis[i]=0;
        S.insert(mp(A[i],i));
    }
    set<pair<int,int> >::iterator it;
    while (!S.empty())
    {
        pair<int,int> x=*S.begin();
        it=S.lower_bound(mp(P-x.first,0));
        if (it!=S.end())
        {
            if (it==S.begin()) it++;
            if (it!=S.end())
            {
                vis[x.second]=1;
                vis[(*it).second]=1;
                ans++;
                S.erase(it);
            }
        }
        S.erase(S.begin());
    }
    f[u][0]=0;
    for (int i=cnt;i>=1;i--)
        if (!vis[i]) { f[u][0]=A[i];break;}
    f[u][1]=ans;
    if (f[u][1]>=m) FLAG=1;
    top=lasttop;
}
bool check(int x)
{
    top=0;
    P=x;
    FLAG=0;
    for (int i=1;i<=n;i++) f[i][0]=f[i][1]=0;
    dfs(1,0);
    return FLAG|(f[1][1]>=m);
}
void erfen(int l,int r)
{
    while (l<r)
    {
        int mid=(l+r+1)>>1;
        if (check(mid)) l=mid;
            else r=mid-1;
    }
    printf("%d\n",l);
}
int main()
{
    scanf("%d%d",&n,&m);
    int sum=0;
    for (int i=1;i<=n-1;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
        sum+=z;
    }
    erfen(0,sum/m+1);
    return 0;
}

评测结果