#include "race.h"
#include<bits/stdc++.h>
using namespace std;
set<pair<int,int>>se[200005];
int aa[200005];
stack<pair<int,int>>st;
map<int,int>ma;
int b;
void dfs1(int x,int y){
aa[x]=1;
// vis[x]=0;
for(auto it=se[x].begin();it!=se[x].end();it++){
if((*it).first!=y){
dfs1((*it).first,x);
aa[x]+=aa[(*it).first];
}
}
}
int dfs2(int x,int y,int pr){
for(auto it=se[x].begin();it!=se[x].end();it++){
if((*it).first!=y){
if(aa[(*it).first]>=aa[pr]/2+aa[pr]%2) return dfs2((*it).first,x,pr);
}
}
return x;
}
int dfs3(int x,int y,int ab,int ac){
// cout<<x<<' '<<ab<<' '<<ac<<"\n";
if(ab>b) return 1e9;
int ret=1e9;
for(auto it=se[x].begin();it!=se[x].end();it++){
if((*it).first!=y){
ret=min(ret,dfs3((*it).first,x,ab+(*it).second,ac+1));
}
}
if(ma[b-ab]!=0)ret=min(ret,ma[b-ab]+ac);
if(ab==b) ret=min(ret,ac);
st.push({ab,ac});
return ret;
}
int rec(int x){
// cout<<x<<' ';
if(se[x].empty()) return 1e9;
dfs1(x,x);
int temp=dfs2(x,x,x),ret=1e9;
queue<pair<int,pair<int,int>>>q;
// vis[temp]=1;
// cout<<x<<' '<<temp<<"\n";
for(auto it=se[temp].begin();it!=se[temp].end();it++){
ret=min(ret,dfs3((*it).first,temp,(*it).second,1));
while(!st.empty()){
if(ma[st.top().first]!=0)ma[st.top().first]=min(st.top().second,ma[st.top().first]);
else ma[st.top().first]=st.top().second;
st.pop();
}
}
ma.clear();
for(auto it=se[temp].begin();it!=se[temp].end();it++){
se[(*it).first].erase({temp,(*it).second});
ret=min(ret,rec((*it).first));
}
return ret;
}
int best_path(int a, int B, int H[][2], int L[])
{
b=B;
for(int i=0;i<a-1;i++){
se[H[i][0]].insert({H[i][1],L[i]});
se[H[i][1]].insert({H[i][0],L[i]});
}
int gah=rec(0);
if(gah==1e9) return -1;
else return gah;
}
