#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,k;
int ANS;
struct muchii{
int x;
int d;
};
vector<muchii> gr[N];
int sz[N];
bool iscentr[N];
void dfs_sz(int nod,int dad){
sz[nod] = 1;
for(auto f:gr[nod]){
if(f.x != dad && iscentr[f.x] == 0){
dfs_sz(f.x,nod);
sz[nod] += sz[f.x];
}
}
}
int findcentr(int nod,int dad, int bigroot){
for(auto f:gr[nod]){
if(f.x != dad && iscentr[f.x] == 0 && sz[f.x] > sz[bigroot]/2)
return findcentr(f.x, nod, bigroot);
}
return nod;
}
void build_dfs(int nod,int dad,int distkm,int dst, map<int,int> &cur){
if(distkm > k)
return;
if(cur.count(distkm))
cur[distkm] = min(cur[distkm], dst);
else
cur[distkm] = dst;
for(auto f:gr[nod]){
if(f.x != dad && iscentr[f.x] == 0){
build_dfs(f.x, nod, distkm + f.d, dst + 1, cur);
}
}
}
void buildcentr(int root){
dfs_sz(root, 0);
int cen = findcentr(root, 0, root);
map<int,int> ansc;
for(auto f:gr[cen]){
if(iscentr[f.x] == 0){
map<int,int> cur;
build_dfs(f.x, cen, f.d, 1, cur);
for(auto x:cur){
if(ansc.count(k - x.first)){
ANS = min(ANS, x.second + ansc[k - x.first]);
}
}
for(auto x:cur){
if(ansc.count(x.first))
ansc[x.first] = min(ansc[x.first], x.second);
else
ansc[x.first] = x.second;
}
}
}
if(ansc.count(k))
ANS = min(ANS, ansc[k]);
iscentr[cen] = true;
for(auto f: gr[cen]){
if(iscentr[f.x] == 0)
buildcentr(f.x);
}
}
int best_path(int _n, int _k, int H[][2], int L[])
{
k = _k;
n = _n;
for(int i=0;i<n-1;i++){
int x, y;
x = H[i][0] + 1;
y = H[i][1] + 1;
gr[x].push_back({y,L[i]});
gr[y].push_back({x,L[i]});
}
ANS = INT_MAX;
buildcentr(1);
if(ANS == INT_MAX)
return -1;
return ANS;
}
