代码

#include<bits/stdc++.h>
#include<bits/extc++.h>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define go(x, i) for(register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define FOR(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define debug(x) cout << #x << " = " << x << endl
#define mem(a, b) memset(a, b, sizeof(a))
#define cpy(a, b) memcpy(a, b, sizeof(a))
#define inf (0x3f3f3f3f)
#define INF (1e18)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define y1 orzorz

typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;
typedef std::pair<ll, int> PLI;
typedef std::pair<int, int> PII;
typedef long double ldb;
typedef double db;

namespace IO {
#define getc() ((S_ == T_) && (T_ = (S_ = Ch_) + fread(Ch_, 1, Buffsize, stdin), S_ == T_) ? 0 : *S_ ++)
#define putc(x) *nowps ++ = (x)

	const uint Buffsize = 1 << 15, Output = 1 << 23;
	static char Ch_[Buffsize], *S_ = Ch_, *T_ = Ch_;
	static char Out[Output], *nowps = Out;

	inline void flush() {fwrite(Out, 1, nowps - Out, stdout); nowps = Out;}
	template<class T>inline bool chkmax(T &_, T __) {return _ < __ ? _ = __, 1 : 0;}
	template<class T>inline bool chkmin(T &_, T __) {return _ > __ ? _ = __, 1 : 0;}

	template<class T>inline void read(T &_) {
		_ = 0; static char __; T ___ = 1;
		for(__ = getc(); !isdigit(__); __ = getc()) if(__ == '-') ___ = -1;
		for(; isdigit(__); __ = getc()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
		_ *= ___;
	}

	template<class T>inline void write(T _, char __ = '\n') {
		if(!_) putc('0');
		if(_ < 0) putc('-'), _ = -_;
		static uint sta[111], tp;
		for(tp = 0; _; _ /= 10) sta[++ tp] = _ % 10;
		for(; tp; putc(sta[tp --] ^ 48)); putc(__);
	}

	inline void procStatus() {
		std::ifstream t("/proc/self/status");
		std::cerr << std::string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
	}
}

using namespace std;
using namespace IO;

const int N = 5e4 + 10;

int to[N << 1], head[N], nxt[N << 1], v[N << 1], e; 
int n, m, f[N], len[N]; 

inline void add(int x, int y, int z) {
	to[++ e] = y; nxt[e] = head[x]; head[x] = e; v[e] = z; 
}

inline void dfs(int x, int dad, int val) {
	multiset<int> S; f[x] = len[x] = 0; 
	go(x, i) if (to[i] ^ dad) {
		dfs(to[i], x, val);
		f[x] += f[to[i]];
		if (len[to[i]] + v[i] >= val) ++ f[x];
		else S.insert(len[to[i]] + v[i]);
	}
	while (!S.empty()) {
		int now = *S.begin(); S.erase(S.begin());
		if (S.lower_bound(val - now) == S.end()) {
			len[x] = now; continue;
		}
		S.erase(S.lower_bound(val - now)), ++ f[x];
	}
}

inline bool check(int x) {
	dfs(1, 0, x);
	return f[1] >= m; 
}

int main() {
#ifdef ylsakioi
	file("5021");
#endif

	read(n), read(m);
	For(i, 2, n) {
		int x, y, z; read(x), read(y), read(z);
		add(x, y, z), add(y, x, z);
	}

	int l = 1, r = 5e8, ans = 1; 
	while (l <= r) {
		int mid = (l + r) >> 1; 
		if (check(mid)) ans = mid, l = mid + 1; 
		else r = mid - 1; 
	}

	write(ans);

	return flush(), 0;
}

评测结果