#include "race.h"
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int sz[200005];
bitset<200005> rm(0);
vector<pair<int,int>> g[200005];
int mn[1000005];
int ans=1e9;
int n,k;
int dfs(int u,int p=0){
sz[u]=1;
for(auto [v,w]:g[u]){
if(v==p||rm[v])
continue;
sz[u]+=dfs(v,u);
}
return sz[u];
}
int centroid(int u,int p,int ts){
for(auto [v,w]:g[u]){
if(v==p||rm[v])
continue;
if(sz[v]*2>ts)
return centroid(v,u,ts);
}
return u;
}
void compute(int u,int p,int t,int dis,int lv){
if(dis>k)
return;
if(t==0)//query
ans=min(ans,lv+mn[k-dis]);
else if(t==1)//update
mn[dis]=min(mn[dis],lv);
else{
mn[dis]=mn[k-dis]=1e9;
}
for(auto [v,w]:g[u])
if(v!=p&&!rm[v])
compute(v,u,t,dis+w,lv+1);
}
void sol(int u){
for(auto [v,w]:g[u])
if(!rm[v])
compute(v,u,2,w,1);
mn[0]=0;
for(auto [v,w]:g[u]){
if(!rm[v]){
compute(v,u,0,w,1);
compute(v,u,1,w,1);
}
}
}
void buildcentroid(int u,int p){
u=centroid(u,0,dfs(u,0));
rm[u]=1;
sol(u);
for(auto [v,w]:g[u])
if(!rm[v])
buildcentroid(v,u);
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
for(int i=0;i<n-1;i++){
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
for(int i=1;i<=1000000;i++)
mn[i]=1e9;
buildcentroid(0,0);
if(ans==1e9)
return -1;
return ans;
}
