好板子的题目。

首先由于 $k, n$ 太大放弃 DP，注意到答案有单调性，那么考虑二分答案。

考虑从叶子开始向上逐层确定是否需要建立消防站，一旦有一个叶子没被覆盖到那么就尽可能往上放一个消防站，容易发现这么贪心是对的。

那么考虑利用回溯来完成这个过程，我们时刻记录子树内离子树根最近消防站的距离，未被覆盖到的最远点离子树根的距离，一旦发现有点未被覆盖，且即使在子树根的父亲上放消防站也覆盖不到，那么就必须在子树根放消防站。

时间复杂度 $O(n \log V)$。

:::info[代码]

namespace LCL {
    constexpr int MAXN = 1e5 + 10, MAXV = MAXN << 2;
    vpii e[MAXN];
    int n, k, ans, now;
    pii dfs(int u, int f, int fw, int lim) {
        int dn = -inf, dh = inf;
        for (auto [v, w] : e[u])
            if (v ^ f) {
                auto [sn, sh] = dfs(v, u, w, lim);
                chkmx(dn, sn + w), chkmn(dh, sh + w);
            }
        if (dh > lim) chkmx(dn, 0);
        if (dn + dh <= lim) dn = -inf;
        if (dn >= 0 && dn + dh > lim && dn + fw > lim) now++, dn = -inf, dh = 0;
        return {dn, dh};
    }
    void main() {
        cin >> n >> k;
        rep(u, 2, n, v, w) cin >> v >> w, e[u].eb(v, w), e[v].eb(u, w);
        int l = 0, r = ans = 1e18;
        while (l <= r)
            if (now = 0, dfs(1, 0, inf, mid), now <= k)
                ans = mid, r = mid - 1;
            else
                l = mid + 1;
        cout << ans << endl;
    }
} // namespace LCL

:::