#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=10000009;
const long long MAXN=200009;
const long long MAXK=1000009;
vector<pair<int,int>> edg[MAXN];
long long pod[MAXN];
long long best[MAXK];
long long version[MAXK];
bool hasBeenCentr[MAXN];
long long k,ans=inf,timer=1;
vector<pair<int,int>> v;
inline long long min1(long long a,long long b)
{
if(a>b)return b;
return a;
}
long long dfs(int curr,int f)
{
pod[curr]=1;
for(auto i:edg[curr])
{
if(i.first==f||hasBeenCentr[i.first])continue;
pod[curr]+=dfs(i.first,curr);
}
return pod[curr];
}
long long centr(int curr,int sz,int f)
{
for(auto i:edg[curr])
{
if(i.first==f||hasBeenCentr[i.first])continue;
if(pod[i.first]>sz/2)return centr(i.first,sz,curr);
}
return curr;
}
void dfsDist(int curr,int dist,int dept,int f)
{
if(dist>k)return;
v.push_back({dist,dept});
if(version[k-dist]!=timer)
{
version[k-dist]=timer;
best[k-dist]=inf;
}
ans=min1(ans,dept+best[k-dist]);
for(auto i:edg[curr])
{
if(i.first==f||hasBeenCentr[i.first])continue;
dfsDist(i.first,dist+i.second,dept+1,curr);
}
}
void centrDec(int curr)
{
dfs(curr,-1);
int cen=centr(curr,pod[curr],-1);
best[0]=0;
version[0]=timer;
for(auto i:edg[cen])
{
v.clear();
if(hasBeenCentr[i.first])continue;
dfsDist(i.first,i.second,1,cen);
for(auto t:v)
{
if(version[t.first]!=timer)
{
version[t.first]=timer;
best[t.first]=inf;
}
best[t.first]=min1(best[t.first],t.second);
}
}
timer++;
hasBeenCentr[cen]=1;
for(auto i:edg[cen])
{
if(hasBeenCentr[i.first])continue;
centrDec(i.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++)
{
edg[H[i][0]].push_back({H[i][1],L[i]});
edg[H[i][1]].push_back({H[i][0],L[i]});
}
centrDec(0);
if(ans==inf)return -1;
return ans;
}
