#include<bits/stdc++.h>
#include "race.h"
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
int ans, k;
vi depth;
vector<map<int,int>>paths;
vector<vector<pi>>adjL;
void dfs(int pos, int prev, int sum) {
paths[pos][sum] = depth[pos];
for(pi adj: adjL[pos]) {
if(adj.first == prev) continue;
depth[adj.first] = depth[pos] + 1;
dfs(adj.first, pos, sum + adj.second);
if(paths[adj.first].size() > paths[pos].size()) swap(paths[adj.first], paths[pos]);
for(auto it = paths[adj.first].begin(); it != paths[adj.first].end(); ++it) {
if(!paths[pos][it->first]) paths[pos][it->first] = it->second;
else paths[pos][it->first] = min(paths[pos][it->first], it->second);
}
}
if(paths[pos][sum+k]) {
int cur = paths[pos][sum+k] - depth[pos];
if(ans == -1) ans = cur;
else ans = min(ans, cur);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = -1, k = K;
paths.resize(N);
depth.assign(N, 0);
adjL.assign(N, vector<pi>());
for(int i=0; i<N-1; ++i) {
adjL[H[i][0]].push_back({H[i][1], L[i]});
adjL[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0,0,0);
if(paths[0][k]) {
int cur = paths[0][k];
if(ans == -1) ans = cur;
else ans = min(ans, cur);
}
return ans;
}
