#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int INF = 1e9;
// -----------------------------------------------------------------------------
int n, k;
struct edge {
int v, w;
edge() = default;
edge(int v, int w): v(v), w(w) {}
};
vector<edge> g[N];
void add(int u, int v, int w) {
g[u].emplace_back(v, w);
}
void Add(int u, int v, int w) {
add(u, v, w), add(v, u, w);
}
int get_root(int);
// -----------------------------------------------------------------------------
int mp[M];
int vis[N], dis[N], dep[N];
int cnt, ans = INF;
void init(int u, int fa, int is, int ep) {
if (is > k) return;
++cnt;
dis[cnt] = is, dep[cnt] = ep;
for (auto t : g[u]) {
if (t.v == fa || vis[t.v]) continue;
init(t.v, u, is + t.w, ep + 1);
}
}
void calc(int u) {
mp[0] = cnt = 0;
for (auto t : g[u]) {
int v = t.v, w = t.w;
if (vis[v]) continue;
int st = cnt + 1;
init(v, u, w, 1);
for (int i = st; i <= cnt; ++i)
ans = min(ans, mp[k - dis[i]] + dep[i]);
for (int i = st; i <= cnt; ++i)
mp[dis[i]] = min(mp[dis[i]], dep[i]);
}
for (int i = 1; i <= cnt; ++i) mp[dis[i]] = INF;
}
void solve(int u) {
vis[u] = 1, calc(u);
for (auto t : g[u]) {
if (vis[t.v]) continue;
solve(get_root(t.v));
}
}
// -----------------------------------------------------------------------------
int siz[N], max_son[N];
int tot, root;
void dfs(int u, int fa) {
siz[u] = 1, max_son[u] = 0;
for (auto t : g[u]) {
int v = t.v;
if (v == fa || vis[v]) continue;
dfs(v, u);
siz[u] += siz[v];
max_son[u] = max(max_son[u], siz[v]);
}
max_son[u] = max(max_son[u], tot - siz[u]);
if (max_son[u] < max_son[root]) root = u;
}
int get_root(int u) {
tot = siz[u], root = 0;
return dfs(u, -1), root;
}
// -----------------------------------------------------------------------------
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> k;
memset(mp, 0x3f, sizeof mp);
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
Add(u + 1, v + 1, w);
}
max_son[0] = n + 1;
siz[1] = n;
solve(get_root(1));
cout << (ans >= n ? -1 : ans) << endl;
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccxGHGnL.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvyndWK.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccvyndWK.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
