#include "race.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int nax=2e5+5;
const int vax=1e6+5;
typedef long long ll;
vector<pair<int,int> > grafo[nax];
int sizes[nax];
int ans=INT_MAX;
int N,K;
int ss,cc;
pair<int,int> m[vax];
vector<pair<int,int> > vv;
bitset<nax> vis;
int in;
void incl(int n, int a, int d, int v){
if(K<v)return;
if(a!=-1){
if(v==K)ans=min(ans,d);
if(m[K-v].s==in)ans=min(ans,m[K-v].f+d);
vv.push_back({v,d});
}
for(auto x:grafo[n]){
if(!vis[x.f]&&x.f!=a){
incl(x.f,n,d+1,v+x.s);
}
if(a==-1){
while(!vv.empty()){
auto p=vv.back();
vv.pop_back();
if(m[p.f].s==in)m[p.f].f=min(m[p.f].f,p.s);
else m[p.f]={p.s,in};
}
}
}
}
int findc(int n, int a, int num){
int s=0;
int mas=0;
for(auto x:grafo[n]){
if(x.f!=a&&!vis[x.f]){
int p=findc(x.f,n,num);
s+=p;
mas=max(mas,p);
}
}
if(mas<=num/2)cc=n;
return s+1;
}
int findsize(int n, int a){
int s=0;
for(auto x:grafo[n]){
if(!vis[x.f]&&x.f!=a){
s+=findsize(x.f,n);
}
}
sizes[n]=s+1;
return s+1;
}
stack<int> cen;
int best_path(int N, int K, int H[][2], int L[]){
::N=N,::K=K;
for(int i=0;i<N-1;i++){
grafo[H[i][0]].push_back({H[i][1],L[i]});
grafo[H[i][1]].push_back({H[i][0],L[i]});
}
for(int i=0;i<vax;i++)m[i]={-1,-1};
findsize(0,-1);
findc(0,-1,N);
cen.push(cc);
while(!cen.empty()){
int n=cen.top();
cen.pop();
in=n;
incl(n,-1,0,0);
vis[n]=1;
for(auto x:grafo[n]){
if(vis[x.f])continue;
findc(x.f,-1,sizes[n]);
cen.push(cc);
}
}
if(ans==INT_MAX)return -1;
return ans;
}
