代码

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <functional>
#include <vector>
#include <limits>
#include <numeric>
#include <queue>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Edge {
    int v, w;
    Edge* next;
};

const int N = 50010;

int n, m, tot, mid, tim;
bool vis[N];
int pool[N];
Edge* g[N];

int dfs(int u);
void adde(int u, int v, int w);
int match(int* arr, int k, int pr);
/*pair<int, int> match(const vector<int>& v);*/

int main() {
//	freopen("track.in", "r", stdin);
//	freopen("track.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    for (int rep = 1; rep < n; ++rep) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adde(u, v, w);
        adde(v, u, w);
    }
    int l = 1, r = 500000000;
    while (l < r) {
        mid = (l + r + 1) / 2;
        tot = 0;
        memset(vis, 0, sizeof(vis));
        tim = 0;
        dfs(1);
        if (tot >= m)
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
    
    return 0;
}

void adde(int u, int v, int w) {
    static Edge pool[N * 2];
    static Edge* p = pool;
    p->v = v;
    p->w = w;
    p->next = g[u];
    g[u] = p;
    ++p;
}

int dfs(int u) {
    vis[u] = true;
    int pl = ++tim, pr = pl;
    for (Edge* p = g[u]; p; p = p->next)
        if (!vis[p->v]) {
            int v = dfs(p->v) + p->w;
            if (v < mid)
                pool[pr++] = v;
            else
                ++tot;
        }
    sort(pool + pl, pool + pr);
    int mm = match(pool + pl, pr - pl, -1);
    tot += mm;
    if (mm * 2 == pr - pl)
        return 0;
    int l = pl, r = pr - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (match(pool + pl, pr - pl, mid - pl) == mm)
            l = mid;
        else
            r = mid - 1;
    }
    return pool[l];
}

int match(int* arr, int k, int pr) {
    int l = 0, r = k - 1, ret = 0;
    for (; r > l; --r) {
        if (r == pr)
            continue;
        while (l == pr || l < r && arr[l] + arr[r] < mid)
            ++l;
        if (l >= r)
            break;
        ++ret;
        ++l;
    }
    return ret;
}

/*
pair<int, int> match(const vector<int>& v) {
    vector<bool> vis(v.size());
    int k = v.size(), cnt = 0;
    int l = 0, r;
    for (r = k - 1; r > l; --r) {
        while (l < r && v[l] + v[r] < mid)
            ++l;
        if (l >= r)
            break;
        vis[l] = true;
        vis[r] = true;
        ++cnt;
        ++l;
    }
    for (int i = k - 1; i >= 0; --i)
        if (!vis[i])
            return make_pair(cnt, v[i]);
    return make_pair(cnt, 0);
}
*/

评测结果