#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 10, maxk = 1e6 + 10;
const int inf = 1e9 + 10;
typedef long long ll;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
struct per_array {
array<Pint, maxk> a = {};
int t = 1;
int& operator[](int i) {
if (a[i].second != t) {
a[i] = {inf, t};
}
return a[i].first;
}
void clear() {
t++;
}
};
vector<Pll> g[maxn];
int w[maxn];
bool used[maxn];
void sizes(int v = 1, int p = -1) {
w[v] = 1;
for (auto [u, _] : g[v]) {
if (u != p && !used[u]) {
sizes(u, v);
w[v] += w[u];
}
}
}
int centroid(int v, int p, int n) {
for (auto [u, _] : g[v]) {
if (u != p && !used[u] && w[u] > n / 2) {
return centroid(u, v, n);
}
}
return v;
}
void dfs(int v, int p, vector<Pll> &t, ll sum, int h = 1) {
if (sum < maxk) {
t.push_back({sum, h});
}
for (auto [u, w] : g[v]) {
if (u != p && !used[u]) {
dfs(u, v, t, sum + w, h + 1);
}
}
}
per_array d;
int solve(int v, int k) {
sizes(v, v);
v = centroid(v, v, w[v]);
used[v] = true;
int ans = inf;
d[0] = 0;
for (auto [u, w] : g[v]) {
if (!used[u]) {
vector<Pll> t;
dfs(u, v, t, w);
for (auto [sum, h] : t) {
if (k - sum >= 0) {
ans = min(ans, (int)h + d[k - sum]);
}
}
for (auto [sum, h] : t) {
d[sum] = min(d[sum], (int)h);
}
}
}
d.clear();
for (auto [u, w] : g[v]) {
if (!used[u]) {
ans = min(ans, solve(u, k));
}
}
return ans;
}
void add_edge(int v, int u, int w) {
g[v].push_back({u, w});
g[u].push_back({v, w});
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; ++i) {
add_edge(H[i][0], H[i][1], L[i]);
}
int ans = solve(1, K);
return (ans == inf ? -1 : ans);
}
