#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back
using ll = int64_t;
vector<vector<pair<int, int>>> graph;
vector<int> sub, blocked;
int n, k;
void prep_sub(int v, int p) {
sub[v] = 1;
for(auto [ s, _ ] : graph[v]) {
if(s == p || blocked[s]) continue;
prep_sub(s, v);
sub[v] += sub[s];
}
}
int find_centroid(int v, int p) {
for(auto [ s, _ ] : graph[v]) {
if(s == p || blocked[s]) continue;
if(sub[s] > n/2) {
return find_centroid(s, v);
}
}
return v;
}
constexpr int inf = 1e9;
vector<pair<int, int>> new_distances;
vector<int> all_distances;
vector<int> minim;
void prep_dist(int v, int p, pair<int, int> dist) {
if(dist.first > k || blocked[v]) return;
new_distances.pb(dist);
for(auto [ s, w ] : graph[v]) {
if(s == p) continue;
prep_dist(s, v, { dist.first + w, dist.second + 1 });
}
}
int res = inf;
void solve(int rep) {
if(blocked[rep]) return;
prep_sub(rep, (-1));
n = sub[rep];
int centroid = find_centroid(rep, (-1));
all_distances = { 0 }, minim[0] = 0;
for(auto [ s, w ] : graph[centroid]) {
prep_dist(s, centroid, { w, 1 });
for(auto [ d, len ] : new_distances) {
res = min(res, minim[k - d] + len);
}
for(auto [ d, len ] : new_distances) {
minim[d] = min(minim[d], len);
all_distances.pb(d);
}
new_distances.clear();
}
for(int d : all_distances) {
minim[d] = inf;
}
blocked[centroid] = 1;
for(auto [ s, _ ] : graph[centroid]) {
solve(s);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
graph.resize(n);
loop(i, 0, n-2) {
graph[H[i][0]].pb({ H[i][1], L[i] });
graph[H[i][1]].pb({ H[i][0], L[i] });
}
minim.resize(k + 1, inf);
blocked.resize(n);
sub.resize(n);
solve(0);
if(res == inf) {
return (-1);
}
else {
return res;
}
}
