b=a+1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50005;
int n, m;
long long w[MAXN];  // w[i] 表示边 i 连接 i 和 i+1 的长度

bool check(long long mid) {
    long long sum = 0;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        sum += w[i];
        if (sum >= mid) {
            cnt++;
            sum = 0;
        }
    }
    return cnt >= m;
}

int main() {
    cin >> n >> m;
    
    // 初始化 w 数组为 0
    for (int i = 1; i <= n; i++) w[i] = 0;
    
    long long total = 0;
    for (int i = 1; i < n; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        // 因为 b_i = a_i + 1，所以边连接的是 a 和 a+1
        // 存储到 w[a] 位置
        w[a] = l;
        total += l;
    }
    
    // 二分答案
    long long left = 0, right = total, ans = 0;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

n==1

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 50005;
vector<pair<int, int>> tree[MAXN];
int n, m;
long long dist[MAXN];

void dfs(int u, int fa) {
    for (auto [v, w] : tree[u]) {
        if (v == fa) continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
}

int main() {
    cin >> n >> m;  // m = 1
    for (int i = 1; i < n; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        tree[a].push_back({b, l});
        tree[b].push_back({a, l});
    }

    // 第一次 DFS：从 1 出发找最远点
    memset(dist, 0, sizeof(dist));
    dfs(1, 0);
    int p = 1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[p]) p = i;
    }

    // 第二次 DFS：从 p 出发找最远点，得到直径长度
    memset(dist, 0, sizeof(dist));
    dfs(p, 0);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dist[i]);
    }

    cout << ans << endl;
    return 0;
}

$O(o(n)logNlogn)$

根据题目描述，很容易想到二分答案，当我们的道路越长，那么m就会越小，否则m就会更大，所以我们需要找到一个满足m的最长的道路

接下来如何去判断当前是否满足要求，我们可以从上往下搜索，对于每棵子树，我们优先去内部匹配，然后把没有匹配的最大值传到父亲节点，继续匹配。

#include<bits/stdc++.h>
using namespace std;
const int N=50010,INF=1e9;
typedef pair<int,int> PII;
#define x first
#define y second
int n,m;
vector<PII> g[N];
int ans;
int calc(vector<int> &q,int len,int k)
{
    int res=0;
    for(int i=q.size()-1,j=0;i>=j;i--)
    {
        if(i==k) continue;
        if(q[i]>=len)
        {
            res++;
        }
        else
        {
            while(j<i&&(j==k||q[i]+q[j]<len)) j++; //q[j]太小了
            if(j<i) //找到一组解
            {
                res++;
                j++;
            }
        }
    }
    return res;//返回可以凑成的长度为len的段数
}
int dfs(int u,int fa,int len) //递归搜索整个结构
{
    vector<int> q;
    for(auto t:g[u])
    {
        if(t.x==fa) continue;
        q.push_back(dfs(t.first,u,len)+t.y);
    }
    if(q.empty()) return 0;
    sort(q.begin(),q.end());//排序
    int mx=calc(q,len,-1);//计算不删除的最大组数
    ans+=mx;
    int l=0,r=q.size()-1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(calc(q,len,mid)==mx) l=mid; //说明当前l是可以删除的
        else r=mid-1;
    }
    if(calc(q,len,r)!=mx) return 0;//说明删除了以后答案不准确了
    return q[r];//可以删除r
}
bool check(int len)
{
    ans=0;
    dfs(1,-1,len);
    return ans>=m;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++) //建图
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    int l=0,r=INF;
    while(l<r) //二分查找最大值
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",r);
    return 0;
}