记录编号	596475	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]赛道修建	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	3.187 s
提交时间	2024-10-28 18:12:57	内存使用	7.25 MiB

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define int long long
using namespace std;
auto IN = freopen("2018track.in", "r", stdin);
auto OUT = freopen("2018track.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 5e4 + 5;
int n = mread(), m = mread(), f[N][2];
// i 子树，0 存最多几条符合条件的道路，1 存在符合条件的道路尽量多的基础上最长的一段赛道
vector<pair<int, int> > v[N];
void dfs(int x, int fa, int &mid){
    int sum = 0;
    multiset<int> se;
    for(auto t : v[x]){
        int y = t.fi;
        if(y == fa){
            continue;
        }
        dfs(y, x, mid);
        sum += f[y][0];
        if(f[y][1] + t.se >= mid){
            sum ++;
        }
        else{
            se.insert(f[y][1] + t.se);
        }
    }
    while(se.size()){
        int t = *se.begin();
        auto it = se.lower_bound(mid - t);
        if(it == se.begin()){
            it ++;
        }
        if(it != se.end()){
            sum ++;
            se.erase(it);
            se.erase(se.begin());
        }
        else{
            f[x][1] = t;
            se.erase(se.begin());
        }
    }
    f[x][0] = sum;
    return;
}
bool check(int mid){
    memset(f, 0, sizeof(f));
    dfs(1, 0, mid);
    return f[1][0] >= m;
}
signed main(){
    for(int i = 1, x, y, z; i < n; i ++){
        cin >> x >> y >> z;
        v[x].push_back(mp(y, z));
        v[y].push_back(mp(x, z));
    }
    int l = 1, r = 0x3f3f3f3f;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    printf("%lld", l);
    return 0;
}