#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> adjlist; //n,l
vector<set<pair<ll,ll>>*> vset; //height,numnodes
vector<ll> prefsum;
vector<ll> height;
ll n,k;
ll INF = 1e18;
void dfs(ll node, ll par){
for (auto p : adjlist[node]){
if (p.first==par){continue;}
prefsum[p.first]=prefsum[node]+p.second;
height[p.first]=height[node]+1;
dfs(p.first,node);
}
}
ll minval(ll node, ll par){
if (adjlist[node].size()==1&&par!=-1){
////cout<<"x\n";
vset[node]=new set<pair<ll,ll>>();
vset[node]->insert({prefsum[node],height[node]});
return INF;
}
ll mxv = INF;
ll mxind = -1;
ll mxsize = -1;
for (auto p : adjlist[node]){
ll i = p.first;
if (i==par){continue;}
mxv=min(mxv,minval(i,node));
ll vs = vset[i]->size();
////cout<<vs<<" "<<mxsize<<'\n';
if (vs>mxsize){
mxind=i;
mxsize=vs;
}
}
////cout<<mxind<<' '<<mxsize<<'\n';
//merge everything llo vset[i]
ll kv = (par==-1)?k:(k+2*prefsum[node]);
for (auto p : adjlist[node]){
ll i = p.first;
if (i==par||i==mxind){continue;}
for (auto hn : *vset[i]){
ll heightfind = kv-hn.first;
//can we find heightfind?
auto f = vset[mxind]->lower_bound({heightfind,0});
if (f!=vset[mxind]->end()&&f->first==heightfind){
mxv=min(mxv,hn.second+f->second-2*height[node]);
}
vset[mxind]->insert(hn);
}
}
//cout<<"check "<<k+prefsum[node]<<'\n';
/*for (auto p : *vset[mxind]){
//cout<<p.first<<" "<<p.second<<", ";
}//cout<<'\n';*/
auto f = vset[mxind]->lower_bound({k+prefsum[node],-1});
if (f!=vset[mxind]->end()&&f->first==k+prefsum[node]){
mxv=min(mxv,f->second-height[node]);
}
vset[node]=vset[mxind];
vset[node]->insert({prefsum[node],height[node]});
//cout<<node<<" "<<par<<": "<<mxv<<'\n';
return mxv;
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;k=K;
adjlist.resize(n);
for (ll i = 0; i<n-1; i++){
adjlist[H[i][0]].push_back({H[i][1],L[i]});
adjlist[H[i][1]].push_back({H[i][0],L[i]});
}
vset.resize(n,NULL);
prefsum.resize(n,0);
height.resize(n,0);
dfs(1,-1);
ll mv = minval(1,-1);
return (mv==INF)?-1:mv;
}
