#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int MXN = 2e5 + 10;
const int MXK = 1e6 + 10;
const int inf = 1e9;
vector<pair<int, int>> lst[MXN];
bool dead[MXN];
int sz[MXN], min_edges[MXK];
int ans, k;
void get_sz(int u, int p = -1) {
sz[u] = 1;
for (auto [v, wt] : lst[u]) {
if (v != p and !dead[v]) {
get_sz(v, u);
sz[u] += sz[v];
}
}
}
int get_cen(int u, int tot, int p = -1) {
for (auto [v, wt] : lst[u]) {
if (v != p and !dead[v] and sz[v] > tot / 2) {
return get_cen(v, tot, u);
}
}
return u;
}
void get_paths(int u, int p, int len, int cnt, vector<pair<int, int>> &path) {
if (len > k) return;
path.push_back({len, cnt});
for (auto [v, wt] : lst[u]) {
if (v != p and !dead[v]) {
get_paths(v, u, len + wt, cnt + 1, path);
}
}
}
void calc(int cen) {
vector<int> mod;
for (auto [v, wt] : lst[cen]) {
if (dead[v]) continue;
vector<pair<int, int>> path;
get_paths(v, cen, wt, 1, path);
for (auto [len, cnt] : path) {
if (len > k) continue;
int rem = k - len;
if (min_edges[rem] != inf) {
ans = min(ans, cnt + min_edges[rem]);
}
}
for (auto [len, cnt] : path) {
if (min_edges[len] == inf) {
mod.push_back(len);
min_edges[len] = cnt;
} else {
min_edges[len] = min(min_edges[len], cnt);
}
}
}
for (auto len : mod) {
min_edges[len] = inf;
}
}
void decomp(int u) {
get_sz(u);
int tot = sz[u];
int cen = get_cen(u, tot);
calc(cen);
dead[cen] = true;
for (auto [v, wt] : lst[cen]) {
if (!dead[v]) {
decomp(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
ans = inf;
for(int i = 0; i <= N; i++) {
lst[i].clear();
dead[i] = false;
}
for (int i = 0; i < N - 1; ++i) {
lst[H[i][0]].push_back({H[i][1], L[i]});
lst[H[i][1]].push_back({H[i][0], L[i]});
}
min_edges[0] = 0;
for (int i = 1; i < MXK; ++i) {
min_edges[i] = inf;
}
decomp(0);
if (ans == inf) {
return -1;
} else {
return ans;
}
}
