#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int n, k, ans=INT_MAX;
vector<vector<pair<int, int>>> adj;
vector<int> sz, centro;
vector<int> mp;
void dfs(int u, int p=-1) {
sz[u]=1;
for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
dfs(v, u);
sz[u]+=sz[v];
}
}
int get_centroid(int u, int p, int obj) {
for (auto [v, w]: adj[u]) if (v!=p && !centro[v] && sz[v]>=obj) return get_centroid(v, u, obj);
return u;
}
void calc(int u, int p, int d, int sm, bool filling) {
if (sm>k) return;
if (filling) mp[sm]=min(mp[sm], d);
else ans=min(ans, mp[k-sm]+d);
for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) calc(v, u, d+1, sm+w, filling);
}
void res(int u, int p, int sm) {
if (sm>k) return;
mp[sm]=INT_MAX
for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) res(v, u, sm+w);
}
int decompo(int u) {
dfs(u);
int c=get_centroid(u, -1, sz[u]/2); centro[c]=1;
mp.clear(), mp[0]=0;
for (auto [v, w]: adj[c]) if (!centro[v]) calc(v, c, 1, w, 0), calc(v, c, 1, w, 1);
for (auto [v, w]: adj[c]) if (!centro[v]) res(v, c, w);
for (auto [v, w]: adj[c]) if (!centro[v]) decompo(v);
return c;
}
int best_path(int N, int K, int H[][2], int L[]) {
n=N, k=K;
adj.resize(n);
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]});
}
sz.resize(n), centro.resize(n), mp.resize(k+1, INT_MAX);
decompo(0);
if (ans==INT_MAX) return -1;
return ans;
}
