#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int k;
int res = pow(10, 9);
vector<vector<pair<int,int>>> g;
vector<bool> cut;
vector<int> s;
vector<unordered_map<int,int>> d;
void dfs(int cur, int p){
s[cur] = 1;
for (auto [next, l] : g[cur]){
if (next == p || cut[next]) continue;
dfs(next, cur);
s[cur] += s[next];
}
}
void dfs2(int cur, int p, int st, int dist, int ul){
if (dist > k) return;
if (dist == k) res = min(res, ul);
if (d[st].find(dist) == d[st].end()) d[st][dist] = ul;
else d[st][dist] = min(d[st][dist], ul);
for (auto [next, l] : g[cur]){
if (next == p || cut[next]) continue;
dfs2(next, cur, st, dist+l, ul+1);
}
}
int centroid(int cur){
dfs(cur, cur);
if (s[cur] <= 2) return cur;
int lim = s[cur]/2;
int par = cur;
while (true){
int bo = -1;
for (auto [next, l] : g[cur]){
if (next == par || cut[next]) continue;
if (s[next] >= lim) bo = next;
}
if (bo == -1) break;
par = cur;
cur = bo;
}
return cur;
}
void solve(int cur){
int x = centroid(cur);
unordered_map<int,int> um;
for (auto [next, l] : g[x]){
if (cut[next]) continue;
d[next].clear();
dfs2(next, x, next, l, 1);
if (!um.empty()){
for (auto [dist, ul] : d[next]){
if (um.find(k-dist) != um.end()) res = min(res, ul+um[k-dist]);
}
}
for (auto [dist, ul] : d[next]){
if (um.find(dist) == um.end()) um[dist] = ul;
else um[dist] = min(um[dist], ul);
}
}
cut[x] = true;
for (auto [next, l] : g[x]){
if (!cut[next]) solve(next);
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
g.resize(N);
for (int i=0; i<N-1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
cut.resize(N, false);
s.resize(N);
d.resize(N);
solve(0);
if (res == pow(10, 9)) return -1;
return res;
}
