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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
struct Edge {int v, w;};
vector<Edge> G[MAXN];
int N, M, L, cnt;
int f[MAXN];
inline bool cmp(int a, int b) {return a > b;}
inline void dfs(int u, int fa) {
multiset<int> s;
for (vector<Edge>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = it -> v, w = it -> w;
if (v == fa) continue;
dfs(v, u);
if (f[v] + w >= L) cnt++;
else s.insert(f[v] + w);
}
while (!s.empty()) {
multiset<int>::iterator it = s.begin();
s.erase(it);
multiset<int>::iterator it1 = s.lower_bound(L - *it);
if (it1 == s.end())
f[u] = max(f[u], *it);
else {
cnt++;
s.erase(it1);
}
}
}
inline bool check() {
memset(f, 0, sizeof(f));
cnt = 0;
dfs(1, 0);
if (cnt >= M) return 1;
return 0;
}
int main() {
scanf("%d%d", &N, &M);
for (register int i = 1; i < N; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back((Edge){v, w});
G[v].push_back((Edge){u, w});
}
int l = 0, r = 500000000;
int ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
L = mid;
if (check()) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%d", ans);
return 0;
}
|