【正经题解】赛道修建

这道题是一个优化问题，我们需要设计一种赛道修建的方案，使得修建的 $m$ 条赛道中长度最小的赛道长度最大。问题的核心在于找 到一种赛道划分方案，使得最小赛道的长度尽可能大。
解题思路如下：
输入处理： 读取输入，构建无向图，表示城市中的路口和道路。同时，计算每个节点到其他节点的最短路径长度。
二分搜索： 通过二分搜索来确定最小赛道长度的最大值。二分的范围为路口到路口最短路径的最大值到总路径长度的最大值。
$DFS$ 计算赛道长度： 设计深度优先搜索函数，计算以每个节点为起点的赛道长度。在搜索的过程中，使用 $multiset$ 存储每个 节点的子树中所有赛道长度，以便找到最小的赛道长度。
$Checker$ 函数判定条件： 在深度优先搜索的过程中，统计满足条件的赛道数量。条件是赛道长度不小于当前二分搜索的值。如果满 足条件的赛道数量大于等于 $m$ ，则说明当前二分搜索的值可行，否则不可行。
输出结果： 输出最终确定的最小赛道长度的最大值。

#include<bits/stdc++.h> 
using namespace std;

const int MAX_N = 50004;

// 读取输入的快捷函数
inline int read() {
    char ch = getchar();
    int res = 0, f = 1;
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        res = (res << 3) + (res << 1) + (ch ^ 48);
        ch = getchar();
    }
    return res * f;
}

int n, m, adj[MAX_N], l, r, nxt[MAX_N << 1], to[MAX_N << 1], val[MAX_N << 1], cnt, dis[MAX_N];

// 添加边的函数
inline void addedge(int u, int v, int w) {
    nxt[++cnt] = adj[u];
    adj[u] = cnt;
    to[cnt] = v;
    val[cnt] = w;
}

multiset<int> s[MAX_N];
multiset<int>::iterator it;
int fpl;
int shx;

// 深度优先搜索，计算每个节点到其他节点的最短路径长度
int dfs(const int &u, const int &fa) {
    s[u].clear();
    for (int e = adj[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == fa) continue;
        int bac = dfs(v, u) + val[e];
        if (bac >= shx) ++fpl;
        else s[u].insert(bac);
    }
    int maxn = 0;
    while (!s[u].empty()) {
        if (s[u].size() == 1) {
            return max(maxn, *s[u].begin());
        }
        it = s[u].lower_bound(shx - *s[u].begin());
        if (it == s[u].begin() && s[u].count(*it) == 1) it++;
        if (it == s[u].end()) {
            maxn = max(maxn, *s[u].begin());
            s[u].erase(s[u].find(*s[u].begin()));
        } else {
            fpl++;
            s[u].erase(s[u].find(*it));
            s[u].erase(s[u].find(*s[u].begin()));
        }
    }
    return maxn;
}

// 检查当前赛道长度是否满足要求
inline bool checker(const int &k) {
    shx = k;
    fpl = 0;
    dfs(1, 0);
    return fpl >= m;
}

// 二分搜索解决问题
inline void solve() {
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (checker(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << ans;
}

// 计算每个节点到其他节点的最短路径长度
void computeDistances(int u, int fa) {
    for (int e = adj[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == fa) continue;
        dis[v] = dis[u] + val[e];
        computeDistances(v, u);
    }
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        r += w;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    computeDistances(1, 0);
    int dw = 0, de = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[i] > dw) de = dw, dw = dis[i];
        if (dis[i] < dw && dis[i] > de) de = dis[i];
    }
    r = de + dw;
    solve();
    return 0;
}