Statement

一棵带边权的树，在树上选出 $m$ 条互不相交的链（点可以重合，但是边不能重合），使得 $m$ 条链中最短的链最长。

$2\leq n\leq 5e4,1\leq m\leq n-1$ .

Thoughts & Solution

看到“最短的链最长”就很容易想到二分。二分一个最短链长，然后看能否组成至少 $m$ 条互不相交的长度不小于 $mid$ 的链即可。

现在的问题就是如何判定了。我们定义“一条链对答案有贡献”表示，这条链的链长不小于当前枚举的最小值。

考虑一条链是如何被组成的。

对于一棵子树 $u$ ，显然通过根节点 $u$ 向上拼接的链最多只能有一条，因此让链尽可能在子树内贡献更多的答案而不是往上走显然是不会更劣的。

那么正解就来了。我们可以用 DP 处理出这个向上走的链长。令 $f[u]$ 为以 $u$ 为根的子树中，最优的不完整链长（就是通过根节点向上拼接的链）（完整的部分就是链长 $\ge mid$ 的，已经贡献到答案里面去了）。

暂时不考虑根节点 $u$ ，对于 $u$ 的所有儿子，如果能单独贡献就直接计入答案。否则，尝试两两合并这些子树中向上走的链（因为点是可以重合的，在根节点合并多少都没有关系），如果长度 $\ge mid$ 就一样计入答案。最后剩下的链中，取一条最长的（也就最容易产生贡献）走过根节点，计入 $f[u]$ 并往上走。

具体实现就可以直接对子树中所有的链长升序排序，然后倒序枚举，对于每一条链找一条 能匹配出 $\ge mid$ 的链中最短的一条链 进行拼接，计入答案即可。最后把剩下的链中的最大值转移给 $f[u]$ .

但是要注意一点，你贪心两两匹配子树中的链，最后得到的只是“能匹配的最大对数”，而不是“能匹配的最优方案”。所以要在得到这个最大对数之后，再来一次二分，找一个最大的 mid 使得 去掉这个mid之后，剩下的部分仍然能匹配出这个最大对数。那么最后得到的 mid 就是要计入 $f[u]$ 中的值。

//Author: RingweEH
const int N=5e4+10;
struct edge
{
    int to,nxt,val;
}e[N<<1];
int n,m,tot=0,head[N],res,f[N];
vector<int> son[N];

void add( int u,int v,int w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].val=w;
}

int get_pair( int u,int pos,int num,int lim )       //在去掉pos这个数之后，所能匹配出的最大对数
{
    int now_res=0,l=0;
    for ( int r=num-1; r; r-- )
    {
        r-=(r==pos);
        while ( l<r && son[u][l]+son[u][r]<lim ) l++;
        l+=(l==pos);
        if ( l>=r ) break;
        now_res++; l++;
    }
    return now_res;
}

void dfs( int u,int fa,int lim )
{
    son[u].clear();
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to; if ( v==fa ) continue;
        dfs( v,u,lim );  f[v]+=e[i].val;
        if ( f[v]>=lim ) res++;
        else son[u].push_back( f[v] );
    }
    //将所有子树上来的链拉到根节点，并判断是否可以独自产生贡献，如果不能那么放入配对序列
    int num=son[u].size(); sort( son[u].begin(),son[u].end() );
    int l=0,r=num-1,cnt=0;
    for ( ; r; r-- )
    {
        while ( l<r && son[u][l]+son[u][r]<lim ) l++;
        if ( l>=r ) break;
        cnt++; l++;  
    }
    //配对过程，cnt就是得到的最大对数。
    res+=cnt;
    if ( cnt*2==num ) { f[u]=0; return; }       //全配完了，不需要再往上转移
    l=0; r=num-1; int now_res=0;
    while ( l<=r )
    {
        int mid=(l+r)>>1,now=get_pair( u,mid,num,lim );
        if ( now==cnt ) now_res=mid,l=mid+1;
        else r=mid-1;
    }
    //二分转移上去的最大链长，使得剩下的链仍能满足最大匹配
    f[u]=son[u][now_res];
}

bool check( int mid )
{
    memset( f,0,sizeof(f) );
    res=0; dfs( 1,0,mid );
    return (res>=m) ? 1 : 0;
}

int main()
{
freopen( "track.in","r",stdin );  freopen( "track.out","w",stdout ); 

    n=read(); m=read(); int r=0;
    for ( int i=1,u,v,w; i<n; i++ )
        u=read(),v=read(),w=read(),add( u,v,w ),r+=w;

    int l=0,ans=0; r=r/m;
    while ( l<=r )
    {
        int mid=(l+r)>>1;
        if ( check(mid) ) ans=mid,l=mid+1;
        else r=mid-1;
    }

    printf( "%d\n",ans );

fclose( stdin ); fclose( stdout );
    return 0;
}