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 59
| #include<bits/stdc++.h> using namespace std;
const int N = 5e4 + 5; int n, m, mid, cnt, tot, head[N]; struct E { int nxt, v, w; }e[N << 1];
void add(int a, int b, int c) { e[++tot] = E{head[a], b, c}; head[a] = tot; e[++tot] = E{head[b], a, c}; head[b] = tot; }
#define IT multiset<int>::iterator
int dfs(int u, int fa) { multiset<int> s; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v, w = e[i].w; if (v == fa) continue; int d = dfs(v, u) + w; if (d >= mid) cnt++; else s.insert(d); } int mx = 0; while (!s.empty()) { IT it = s.begin(); int x = *it; s.erase(it); IT t = s.lower_bound(mid - x); if (t == s.end()) mx = x; else s.erase(t), cnt++; } return mx; }
int main() { freopen("track.in", "r", stdin); freopen("track.out", "w", stdout); int l = 0, r = 0, ans = 0; scanf("%d %d", &n, &m); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); add(u, v, w); l = min(l, w); r += w; } while (l <= r) { mid = (l + r) >> 1; cnt = 0; dfs(1, 0); if (cnt >= m) l = mid + 1, ans = mid; else r = mid - 1; } printf("%d\n", ans); return 0; }
|