思路

• 二分答案：对 $D$ 二分，检查是否能用不超过 $k$ 次删边，使所有连通块直径 $\le D$。

• 可行性检查（贪心 + 树形 DP，自底向上）：

  • 固定根（任意如 1），一次性预处理父子关系与后序序列。

  • 对每个节点，把每个子树向上“贡献”的路径长度记为 $t = \text{up}[v] + w(u,v)$。

    • 若 $t > D$，该子边必须切断（计一次删除）。
    • 否则加入数组 $A$。

题目内容

在一颗覆盖全国的光纤通信网络中， $n$ 条光纤节点按照道路连接形成一棵无向树。相邻节点之间的光纤长度记为 $w_e$ 。长距离信号衰减明显，为了提升整体质量，工程师计划在不改变节点位置的前提下，将网络切割成若干段，使得每一段内部的最远通信距离(即直径)都不超过某个值。

具体来说，工程师可以拆除至多 $k$ 条光纤(删除对应的边)，从而把原树分成至多 $k+1$ 个连通部分。定义一棵树(或连通部分)的 直径 为该部分中两点间最短路径的最大长度，即所有路径长度之 $max$ 。

请你计算：在最多拆除 $k$ 条光纤的前提下，所能得到的最小可能最大直径值。也就是说，你需要给出一个整数 $D$ ，满足：

• 经过不超过 $k$ 次拆除操作后，所有连通部分的直径 $≤ D^*$ ;

• 并且不存在更小的整数满足上述条件

【名词解释】

• 树：树是一种无向、连通且无环的图结构。

• 直径：对一棵树(连通部分)，其直径指树中两点间最短路径长度的最大值。

输入描述

第一行输入两个整数 $n$ 和 $k(2≤n≤2×10^5，0≤k≤n-1)$ ，分别表示网络的节点数量与最多可拆除的光纤数量。

接下来 $n-1$ 行，每行输入三个整数 $u_i,v_i,w_i(1≤ u_i,v_i≤n,u_i ≠ v_i,1≤w_i≤10^9)$ ，表示一条长度为 $w_i$ 的光纤连接节点 $u_i$ 与 $v_i$ 。

输入保证所有节点形成一棵树。

输出描述

输出一个整数，表示拆除不超过 $k$ 条光纤后，所有连通部分可能达到的最小最大直径。

样例1

输入

5 1
1 2 1
2 3 2
3 4 2
4 5 1

输出

3

说明

说明：若拆除边 $(3,4)$，两段子树分别包含节点 {$1,2,3$} 与 {$4,5$}，其直径分别为 $1+2=3$ 与 $1$ ，因此最大直径为 $3$ 且无法做到更小。

样例2

输入

7 2
1 2 5
2 3 4
2 4 3
4 5 2
4 6 2
6 7 1

输出

5