形式化题目

给定一棵 $n$ 个结点的树，每条边有一个正整数长度。要求选出 $m$ 条树上的简单路径（每条边至多属于一条路径），使得其中最短的路径长度尽可能大。求这个最大值。

样例 2 推演（$m = 3$，边长标在图上）：

flowchart TD
    A(("1")) ---|"6"| B(("2"))
    B ---|"3"| C(("3"))
    C ---|"5"| D(("4"))
    D ---|"10"| E(("5"))
    B ---|"4"| F(("6"))
    B ---|"9"| G(("7"))
    D ---|"7"| H(("8"))
    D ---|"4"| I(("9"))

把边长加起来容易验证：路径 $1 \to 7$ 长 $15$，路径 $6 \to 3 \to 4 \to 9$ 长 $16$，路径 $8 \to 5$ 长 $17$，三条路径两两不共用边，最短的是 $15$——这也是所有方案里的最大值。

正解

思路

第一步：把"最短的最长"变成判定问题。 直接决定 $m$ 条赛道怎么走很难，但如果我们先假设一个目标长度 $\mathrm{limit}$，问题就变成了一个判断题：

能否在树上选出 $m$ 条边互不重叠的简单路径，每条长度都 $\geqslant \mathrm{limit}$？

这个判定有一个关键的单调性：$\mathrm{limit}$ 越大，能修出的赛道条数只会越少。于是"能修出 $m$ 条 $\geqslant \mathrm{limit}$ 的赛道"对 $\mathrm{limit}$ 单调，可以二分答案：二分 $\mathrm{limit} \in [1, \sum l_i]$，找到满足条件最大的 $\mathrm{limit}$ 输出即可。剩下的问题只有一个——如何在树上一遍算出"$\geqslant \mathrm{limit}$ 的不重叠路径最多有几条"。

第二步：树形贪心求最大条数。 任取一个结点为根，自底向上处理。对每个结点 $u$，它的子树里能凑出的赛道只有两类：

1. 完全落在子树内的赛道，在处理 $u$ 之前就结算掉；
2. 一端在 $u$ 的子树里、另一端向父亲延伸的"半成品"：从某个子孙出发走到 $u$ 的一条单链，它是该子树中某点跳到 $u$、再到祖先的路径前缀。

于是每个结点只需向父亲汇报一个信息：子树伸上来的单链。这些单链两两之间可以在 $u$ 处拼起来（两条单链首尾相接，就得到一条完整的赛道），也可以被父亲继续延长。设处理 $u$ 时收到的单链长度列表为 $\mathrm{rests}$（每条是"子结点传上来的链 + 到 $u$ 的那条边"）：

• 某条链长度已经 $\geqslant \mathrm{limit}$：它自己就是一条完整赛道，直接结算。不用再管它——留一条链去配它，纯属浪费（对方被白吃掉）。
• 其余的链长度都 $< \mathrm{limit}$，单干不行，只能两两拼。把 $\mathrm{rests}$ 排序，双指针从两端向中间扫：最短 + 最长若能凑到 $\mathrm{limit}$，就配对成一条赛道；否则最短的那条谁也配不上（它和最长的都不行，和别的更不行），只能弃掉。这就是经典的救生艇贪心，能证明配出的是最多的对数。

未配对、未被弃掉的链里，最长的那条作为 $u$ 向父亲汇报的"剩余单链"——传得越长，将来在祖先那里被拼成赛道的希望越大。

两个易错的实现细节（都踩过坑）：

• 弃掉不等于永远消失。 若 $u$ 处所有链恰好两两配满，双指针结束时刻意不剩链，但一个"最长被弃链"其实值得一记：比如单链 $\{6, 5, 3\}$、$\mathrm{limit} = 8$，贪心配出 $(3,6)$ 后什么都不传，可 $6$ 本身留在 $\mathrm{rests}$ 里若改配 $(3,5)$，就能把 $6$ 传上去。正确写法是：配对数取最大 $p$，在此前提下"弃掉"的链里取最长的；由于交换论证可证"弃掉较大的链、留下较小的"只会让配对更难，能弃的最大值随被弃链的下标单调，所以对弃谁再套一个二分，找到删掉后仍配得出 $p$ 对的最长链即可（全配满时记 $0$）。

• $\geqslant \mathrm{limit}$ 的链直接单干结算，不能参与配对后再被"剩下"——这是第一版贪心漏掉的情况，导致长链被无辜配对、答案偏小。

整个流程用一张图总结：

flowchart TD
    A["二分 limit"] --> B["树上判定：>= limit 的不重叠路径最多几条?"]
    B --> C{"条数 >= m ?"}
    C -->|"是，越大也行"| D["lo = mid"]
    C -->|"否，太大了"| E["hi = mid - 1"]
    D --> F["输出 lo"]
    E --> A

树形判定的执行顺序：先用一次 BFS 求出"父结点先于子结点"的访问序，再倒序遍历——保证计算某结点时它的所有子结点都已经把单链汇报上来了。$n \leqslant 5 \times 10^4$ 且树可能退化成链，Python 必须避免递归 DFS，这个访问序写法恰好是一棵树的"递归转迭代"。

代码

代码中 max_pairs 是救生艇双指针，pair_chains 负责单个结点的分配并返回 (结算条数, 传给父亲的剩余链)，max_tracks(limit) 就是树形判定本身，主流程是一段标准二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{int v; ll w;};
int max_pairs(vector<ll> rest,ll limit){int i=0,j=(int)rest.size()-1,pairs=0; while(i<j){if(rest[i]+rest[j]>=limit){pairs++;i++;j--;} else i++;} return pairs;}
pair<int,ll> pair_chains(vector<ll> rests,ll limit){int singles=0; vector<ll> rest; for(int i=0;i<(int)rests.size();i++){if(rests[i]>=limit) singles++; else rest.push_back(rests[i]);} sort(rest.begin(),rest.end()); int p=max_pairs(rest,limit); ll leftover=0; int lo=0,hi=(int)rest.size()-1; while(lo<hi){int mid=(lo+hi+1)/2; vector<ll> keep; for(int i=0;i<(int)rest.size();i++) if(i!=mid) keep.push_back(rest[i]); if(max_pairs(keep,limit)>=p) lo=mid; else hi=mid-1;} if(p*2<(int)rest.size() && !rest.empty()) leftover=rest[lo]; return {singles+p,leftover};}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n,m; if(!(cin>>n>>m)) return 0; vector<vector<Edge> > adj(n+1); ll total_len=0; for(int i=0;i<n-1;i++){int a,b; ll l;cin>>a>>b>>l; adj[a].push_back({b,l}); adj[b].push_back({a,l}); total_len+=l;} vector<int> parent(n+1), order; order.push_back(1); for(int idx=0;idx<(int)order.size();idx++){int u=order[idx]; for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; if(v!=parent[u]){parent[v]=u; order.push_back(v);}}} ll lo=1,hi=total_len; while(lo<hi){ll mid=(lo+hi+1)/2; int total=0; vector<ll> up(n+1); for(int idx=(int)order.size()-1;idx>=0;idx--){int u=order[idx]; vector<ll> rests; for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; if(v!=parent[u]) rests.push_back(up[v]+adj[u][i].w);} pair<int,ll> pr=pair_chains(rests,mid); total+=pr.first; up[u]=pr.second;} if(total>=m) lo=mid; else hi=mid-1;} cout<<lo<<'\n'; return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 13:44
# update_at: 2026-10-02 13:44

import sys


def max_pairs(rest: list[int], limit: int) -> int:
    """排序单链里最多能拼出多少对（每对长度和 ≥ limit）：双指针，最短 + 最长能拼就拼。"""
    i, j, pairs = 0, len(rest) - 1, 0
    while i < j:
        if rest[i] + rest[j] >= limit:  # 最短 + 最长能拼就拼，省着用长链
            pairs += 1
            i += 1
            j -= 1
        else:                           # 最短的链已无配对可能
            i += 1
    return pairs


def pair_chains(rests: list[int], limit: int) -> tuple[int, int]:
    """把子树伸上来的单链分配成赛道：≥ limit 的单链独立成赛道，其余两两拼接。

    返回 (本结点确定的赛道条数, 剩余可向父结点延伸的最长单链)。
    配对数取最大 p；在这个前提下传上去的链越长越好，
    而「弃掉较大的链、留下较小的」只会让配对更难（交换论证可证单调），
    所以二分出「删掉它后仍能配出 p 对」的最长链当作剩余。
    """
    singles = sum(c >= limit for c in rests)       # ≥ limit 的链各自独立成赛道
    rest = sorted(c for c in rests if c < limit)   # 全部 < limit，拼不出也不够单干
    p = max_pairs(rest, limit)
    leftover = 0                                   # 恰好全部配满时无剩余链
    lo, hi = 0, len(rest) - 1                      # 谓词随下标单调：删得越大越难配
    while lo < hi:
        mid = (lo + hi + 1) // 2
        keeps = max_pairs(rest[:mid] + rest[mid + 1:], limit) >= p  # 删掉 rest[mid] 还能配 p 对吗
        if keeps:
            lo = mid
        else:
            hi = mid - 1
    if p * 2 < len(rest):                          # 有配不出去的弃链，取能弃的最长的那条
        leftover = rest[lo]
    return singles + p, leftover


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]  # 邻接表：(邻居, 道路长)
    total_len = 0
    for _ in range(n - 1):
        a, b, l = next(data), next(data), next(data)
        adj[a].append((b, l))
        adj[b].append((a, l))
        total_len += l

    # 迭代求「父结点先于子结点」的访问序：n 达 5e4，链形树会把递归爆栈
    parent = [0] * (n + 1)
    order = [1]
    for u in order:  # order 边遍历边增长，父结点必先入序
        for v, _ in adj[u]:
            if v != parent[u]:
                parent[v] = u
                order.append(v)

    def max_tracks(limit: int) -> int:
        """每条赛道长度都 ≥ limit 时，整棵树最多能修出多少条赛道。"""
        total = 0
        up = [0] * (n + 1)  # 结点处拼不出赛道、还能向父结点继续延伸的最长链
        for u in reversed(order):  # 逆序处理，保证算 u 时所有子结点已汇报
            rests = [up[v] + l for v, l in adj[u] if v != parent[u]]
            pairs, longest = pair_chains(rests, limit)
            total += pairs
            up[u] = longest
        return total  # 根结点的剩余链无处延伸，自然作废

    # 二分答案：limit 越大能修的赛道越少，找能满足 m 条的最大 limit
    lo, hi = 1, total_len
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if max_tracks(mid) >= m:
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    solve()

复杂度

• 单次判定：每个结点进队一次，$\mathrm{rests}$ 排序的总代价是 $\sum d_u \log d_u = O(n \log n)$；结点内"弃谁"的二分多乘一层 $\log$，但同样只作用在 $d_u$ 条链上，总计仍 $O(n \log n)$。
• 二分次数：$O(\log \sum l_i) \leqslant O(\log(5 \times 10^4 \times 10^4)) \approx 29$ 次。
• 总复杂度 $O(n \log n \log \sum l_i)$，与 C++ 正解同阶，Python 常数偏大但真实数据全部通过；空间 $O(n)$。

总结

• “最短的最长” → 二分答案 $\mathrm{limit}$，把最优化变成树上判定：$\geqslant \mathrm{limit}$ 的不重叠路径最多能选出几条。
• 树形贪心自底向上：每条子树单链要么自成一赛道（$\geqslant \mathrm{limit}$），要么按救生艇双指针两两拼接；弃链时在配对数不变的前提下二分出能弃的最长链传给父亲。
• 两个坑：$\geqslant \mathrm{limit}$ 的链要直接单干；全配满时别把本可传上去的链弄丢。
• 复杂度 $O(n \log n \log \sum l_i)$。

图示解析

单链在结点处的四种归宿（树形贪心的核心动作）：

以样例 2 走一遍 $\mathrm{limit} = 15$ 的判定（自底向上，省略无事的叶子）：

三处结算共 $3$ 条，恰好等于 $m$，$\mathrm{limit} = 15$ 可行；$\mathrm{limit} = 16$ 时按同样规则只能凑出 $2$ 条，二分收敛到 $15$，正是样例答案。观察重点：结点 $2$ 处那对 $(8, 9)$——它们都不是被弃的"最短链"，只是和为 $17 < \mathrm{limit}$ 不够，这种链越往上传越容易被更高的祖先拼起来，这正是"树形"的意义。