#include "bits/stdc++.h"
#include "race.h"
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 10;
vector<pair<int, int>> adj[MAXN];
vector<int> sz(MAXN);
vector<bool> removed(MAXN);
int K, ans = 1e8;
vector<int> P(MAXN, 1e9 + 7);
int subtree_size(int u, int par = -1) {
sz[u] = 1;
for (auto [v, q] : adj[u]) {
if (v == par || removed[v]) {
continue;
}
sz[u] += subtree_size(v, u);
}
return sz[u];
}
int centroid(int u, int subsz, int par = -1) {
for (auto [v, q] : adj[u]) {
if (v == par || removed[v]) {
continue;
}
if (sz[v] * 2 > subsz) {
return centroid(v, subsz, u);
}
}
return u;
}
void dfs(int u, int par, int dpt, int W) {
if (W > 0 && W <= K) {
P[W] = 1e8;
}
if (K > W) {
P[K - W] = 1e8;
}
for (auto [v, q] : adj[u]) {
if (v == par || removed[v]) {
continue;
}
dfs(v, u, dpt + 1, W + q);
}
}
void dfs0(int u, int par, int dpt, int W) {
if (K >= W && par != -1) {
// cout << par << ' ' << u << ' ' << P[K - W] << ' ' << dpt << '\n';
ans = min(ans, P[K - W] + dpt);
}
for (auto [v, q] : adj[u]) {
if (v == par || removed[v]) {
continue;
}
dfs0(v, u, dpt + 1, W + q);
}
}
void dfs1(int u, int par, int dpt, int W) {
if (K >= W && par != -1) {
P[W] = min(P[W], dpt);
}
for (auto [v, q] : adj[u]) {
if (v == par || removed[v]) {
continue;
}
dfs1(v, u, dpt + 1, W + q);
}
}
void build(int u = 0) {
int c = centroid(u, subtree_size(u));
removed[c] = 1;
for (auto [v, q] : adj[c]) {
if (removed[v]) {
continue;
}
dfs(v, u, 1, q);
}
for (auto [v, q] : adj[c]) {
if (removed[v]) {
continue;
}
dfs0(v, u, 1, q);
dfs1(v, u, 1, q);
}
for (auto [v, q] : adj[c]) {
if (removed[v]) {
continue;
}
build(v);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 0; i < n - 1; i++) {
adj[h[i][0]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
K = k;
P[0] = 0;
build();
if (ans > n) {
return -1;
}
return ans;
}
