思路与算法

二分最短赛道长度X，树上后序汇总子树已成赛道与一条待延长支路。长度已达X的支路直接完成；余下支路按小到大，用最小足够长的伙伴配对，保留最大的未配支路向父亲延伸。

正确性说明

子树与外部只有父边相连，因此至多一条未完成支路有必要向上传递。已达X的支路可独立完成。对最短支路，若存在可配伙伴，取最小可行伙伴可以通过交换保持最大配对数，并给剩余长支路保留不更差选择；没有伙伴则只能留下或丢弃。相同完成数下保留最大未配长度最利于祖先。后序归纳得到最大完成数，随X单调二分正确。

复杂度

O(n log n log(S/m))时间、O(n)空间，S为边长总和；每次判定含支路multiset构造与残余数组初始化，遍历顺序仅预处理一次。

易错点

赛道之间不能共边，但可共享结点。父边只接到一条剩余支路上；50000点深链用迭代顺序避免递归溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    long long sum = 0;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        sum += w;
    }
    vector<int> par(n, -1), q(1, 0);
    par[0] = 0;
    for (int i = 0; i < (int)q.size(); i++)
        for (auto e : g[q[i]])
            if (par[e.first] < 0) {
                par[e.first] = q[i];
                q.push_back(e.first);
            }
    auto ok = [&](long long X) {
        vector<long long> rem(n);
        int count = 0;
        for (int z = n - 1; z >= 0; z--) {
            int u = q[z];
            multiset<long long> s;
            for (auto e : g[u])
                if (par[e.first] == u) {
                    long long v = rem[e.first] + e.second;
                    if (v >= X)
                        count++;
                    else
                        s.insert(v);
                }
            long long best = 0;
            while (!s.empty()) {
                long long a = *s.begin();
                s.erase(s.begin());
                auto it = s.lower_bound(X - a);
                if (it != s.end()) {
                    s.erase(it);
                    count++;
                } else
                    best = max(best, a);
            }
            rem[u] = best;
        }
        return count >= m;
    };
    long long lo = 0, hi = sum / m;
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        if (ok(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo << "\n";
}