#include "race.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> v[200001], c[200001], chk1, chk2;
bool visited[200001];
int sz[200001], ans = 1000000000, n, k;
int mindep[1000001], newdep[1000001];
int getSize(int x, int y){
sz[x] = 1;
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && !visited[v[x][i]]) sz[x] += getSize(v[x][i], x);
}
return sz[x];
}
int getCentroid(int x, int y, int z){
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && sz[v[x][i]]*2 > z && !visited[v[x][i]]) return getCentroid(v[x][i], x, z);
}
return x;
}
void dfs(int x, int y, int dep, int cnt){
if(dep == k) ans = min(ans, cnt);
if(dep > k) return;
if(mindep[k-dep] != 1e9) ans = min(ans, cnt + mindep[k-dep]);
newdep[dep] = min(newdep[dep], cnt);
chk1.push_back(dep);
chk2.push_back(dep);
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && !visited[v[x][i]]) dfs(v[x][i], x, dep+c[x][i], cnt+1);
}
}
void dnc(int x){
int cent = getCentroid(x, -1, getSize(x, -1));
for(int i = 0;i < v[cent].size();i++){
if(!visited[v[cent][i]]){
dfs(v[cent][i], cent, c[cent][i], 1);
for(int j = 0;j < chk1.size();j++) mindep[chk1[j]] = min(mindep[chk1[j]], newdep[chk1[j]]);
chk1.clear();
}
}
for(int j = 0;j < chk2.size();j++) mindep[chk2[j]] = newdep[chk2[j]] = 1e9;
chk2.clear();
visited[cent] = true;
for(int i = 0;i < v[cent].size();i++) if(!visited[v[cent][i]]) dnc(v[cent][i]);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0;i < N-1;i++){
v[H[i][0]].push_back(H[i][1]);
c[H[i][0]].push_back(L[i]);
v[H[i][1]].push_back(H[i][0]);
c[H[i][1]].push_back(L[i]);
}
for(int i = 0;i <= K;i++) mindep[i] = newdep[i] = 1e9;
dnc(0);
return ans == 1e9 ? -1 : ans;
}
