#include <bits/stdc++.h>
#include "race.h"
using namespace std;
struct ari{
int v, w;
};
int n, k;
vector<vector<ari>> adj;
int subar[200025];
bool used[200005];
int ans=(1<<30);
int pesos[1000025];
void dfs(int node, int ant){
subar[node]=1;
for(auto h: adj[node]){
if(h.v==ant || used[h.v])
continue;
dfs(h.v, node);
subar[node]+=subar[h.v];
}
}
int centroid(int node, int ant, int tam){
for(auto h: adj[node]){
if(h.v==ant || used[h.v])
continue;
if(subar[h.v]>tam/2)
return centroid(h.v, node, tam);
}
return node;
}
void explora(int node, int cnt, int sum, int ant){
if(sum>k)
return;
subar[node]=1;
if(pesos[sum]==0)
pesos[sum]=cnt;
else
pesos[sum]=min(pesos[sum], cnt);
for(auto h: adj[node]){
if(h.v==ant || used[h.v])
continue;
explora(h.v, cnt+1, sum+h.w, node);
subar[node]+=subar[h.v];
}
}
void checa(int node, int cnt, int sum, int ant){
subar[node]=1;
if(sum>k)
return;
if(k-sum>=0 && pesos[k-sum]!=0)
ans=min(pesos[k-sum]+cnt, ans);
for(auto h: adj[node]){
if(used[h.v] || h.v==ant)
continue;
checa(h.v, cnt+1, sum+h.w, node);
subar[node]+=subar[h.v];
}
if(pesos[sum]==0)
pesos[sum]=cnt;
else
pesos[sum]=min(pesos[sum], cnt);
}
void limpia(int node, int sum, int ant){
if(sum<=1000000)
pesos[sum]=0;
if(sum>k)
return;
for(auto h: adj[node]){
if(h.v==ant || used[node])
continue;
limpia(h.v, sum+h.w, node);
}
}
void busca(int node, int tam){
bool ya=0;
used[node]=1;
for(auto h: adj[node]){
if(used[h.v])
continue;
if(!ya){
explora(h.v, 1, h.w, node);
ya=1;
}
else{
checa(h.v, 1, h.w, h.v);
}
}
if(pesos[k]!=0)
ans=min(ans, pesos[k]);
for(auto h: adj[node]){
if(used[h.v])
continue;
limpia(h.v, h.w, node);
}
for(auto h: adj[node]){
if(used[h.v])
continue;
int cen=centroid(h.v, node, subar[h.v]);
busca(cen, subar[h.v]);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N; k=K;
adj.resize(n+25);
for(int i=0; i<n-1; i++){
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, 0);
int cen=centroid(0, 0, n);
busca(cen, n);
if(ans==(1<<30))
return -1;
return ans;
}
