#include "race.h"
#include <vector>
#include <map>
using namespace std;
#define oo 1000000000
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
int ans = oo;
vector<vector<pii>> ed;
vector<bool> used;
vector<int> size;
vector<pii> v;
void calcSize(int cur, int pr){
size[cur] = 1;
for (auto [x, w] : ed[cur]){
if (used[x] || x == pr) continue;
calcSize(x, cur);
size[cur] += size[x];
}
}
int findCentroid(int cur, int pr, int n){
for (auto [x, w] : ed[cur]){
if (used[x] || x == pr) continue;
if (size[x] > n / 2){
return findCentroid(x, cur, n);
}
}
return cur;
}
void dfs(int cur, int pr, int k, int d, int l){
if (d > k) return;
v.pb({d, l});
for (auto [x, w] : ed[cur]){
if (x == pr || used[x]) continue;
dfs(x, cur, k, d + w, l + 1);
}
}
void calc(int cur, int n, int k){
calcSize(cur, -1);
cur = findCentroid(cur, -1, n);
map<int, int> dp;
used[cur] = true;
for (auto [x, w] : ed[cur]){
v.clear();
dfs(x, cur, k, w, 1);
for (auto [d, l] : v){
if (dp[k - d] == 0 && k - d != 0) continue;
ans = min(ans, l + dp[k - d]);
}
for (auto [d, l] : v){
if (dp[d] == 0) dp[d] = l;
else dp[d] = min(dp[d], l);
}
}
for (auto [x, w] : ed[cur]){
if (used[x]) continue;
calc(x, n, k);
}
}
int best_path(int n, int k, int h[][2], int l[]){
ed.resize(n);
used.resize(n);
size.resize(n);
for (int i = 0; i < n - 1; ++i) {
ed[h[i][0]].pb({h[i][1], l[i]});
ed[h[i][1]].pb({h[i][0], l[i]});
}
calc(0, n, k);
if (ans == oo) ans = -1;
return ans;
}
