#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;
struct Edge{
int x,d;
Edge(){}
Edge(int a, int b){
x = a;
d = b;
}
};
vector<Edge> T[MN];
Edge A[MN][101];
Edge B[101];
int DFS(int i, int val, int dis, int r, int K){
if(dis==K) return val;
if(dis>K) return MN;
int res = MN;
for(auto it : T[i]){
//cout << i << ' ' << it.x << ' ' << r << '\n';
if(it.x==r) continue;
res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
}
return res;
}
int TDP(int i, int r, int K){
int res = MN;
for(auto it : T[i]){
if(it.x==r) continue;
res = min(res,TDP(it.x,i,K));
for(int j=0; j<=K; j++){
if(j+it.d<=K){
int l = A[it.x][j].d+1;
if(l<A[i][j+it.d].d){
B[j+it.d] = A[i][j+it.d];
A[i][j+it.d] = Edge(it.x,l);
}
else if(l<B[j+it.d].d) B[j+it.d] = Edge(it.x,l);
}
}
}
for(int k=0; k<=K; k++){
if(A[i][k].x!=A[i][K-k].x) res = min(res,A[i][k].d+A[i][K-k].d);
else res = min(res,B[k].d+A[i][K-k].d);
B[k].d = MN;
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
int ans = MN;
for(int i=0; i<N-1; i++){
T[H[i][0]].push_back(Edge(H[i][1],L[i]));
T[H[i][1]].push_back(Edge(H[i][0],L[i]));
}
for(int i=0; i<N; i++)
for(int j=1; j<=K; j++){
A[i][j].d = MN;
B[j].d = MN;
}
if(K<=100){
ans = TDP(0,0,K);
}
else{
for(int i=0; i<N; i++){
ans = min(ans,DFS(i,0,0,i,K));
}
}
if(ans==MN) ans = -1;
return ans;
}
