#include <iostream>
#include <queue>
#include <algorithm>
#include "race.h"
using namespace std;
int Ans = 1e9, Min[1<<20], block[1<<20], ch[1<<20], KK;
vector<pair<int,int>> nei[1<<20];
int centroid(int u, int p, int r){
for (auto [i, w] : nei[u]){
if (!block[i] and i != p and ch[i] * 2 > ch[r])
return centroid(i, u, r);
}
return u;
}
void dfs0(int u, int p){
ch[u] = 1;
for (auto [i, w] : nei[u]){
if (!block[i] and i != p)
dfs0(i, u), ch[u] += ch[i];
}
}
void dfs1(int u, int p, int L, int pathLen = 1){
if (L <= KK)
Ans = min(Ans, pathLen + Min[KK - L]);
for (auto [i, w] : nei[u]){
if (!block[i] and i != p)
dfs1(i, u, L + w, pathLen + 1);
}
}
void dfs2(int u, int p, int L, int pathLen = 1){
if (L <= KK)
Min[L] = min(Min[L], pathLen);
for (auto [i, w] : nei[u]){
if (!block[i] and i != p)
dfs2(i, u, L + w, pathLen + 1);
}
}
void dfs3(int u, int p, int L, int pathLen = 1){
if (L <= KK)
Min[L] = 1e9;
for (auto [i, w] : nei[u]){
if (!block[i] and i != p)
dfs3(i, u, L + w, pathLen + 1);
}
}
void dfs(int u){
dfs0(u, u);
int c = centroid(u, u, u);
for (auto [i, l] : nei[c]){
if (!block[i]){
dfs1(i, c, l);
dfs2(i, c, l);
}
}
for (auto [i, l] : nei[c]){
if (!block[i])
dfs3(i, c, l);
}
block[c] = 1;
for (auto [i, l] : nei[c]){
if (!block[i])
dfs(i);
}
}
int best_path(int n, int k, int h[][2], int l[]){
for (int i=0;i<n-1;i++){
nei[h[i][0]].push_back({h[i][1], l[i]});
nei[h[i][1]].push_back({h[i][0], l[i]});
}
KK = k;
// cout<<KK<<endl;
for (int i=1;i<(1<<20);i++)
Min[i] = 1e9;
dfs(0);
if (Ans == 1e9)
Ans = -1;
return Ans;
}
