#include "race.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
long long n,k,p[200007],sz[200007];
gp_hash_table<long long,long long>cnt;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
long long operator()(pair<int,int> x) const { return ((long long)(x.first)<<(19LL))^(x.second)^RANDOM; }
};
unordered_set<pair<int,int>, chash> edges[200007];
long long trueans;
void dfs(long long i,long long p)
{
sz[i]=1;
for(auto [el,_]:edges[i])
{
if(el==p)
{
continue;
}
dfs(el,i);
sz[i]+=sz[el];
}
}
long long find(long long i,long long p,long long all)
{
long long maxx=0,to=0;
for(auto [el,_]:edges[i])
{
if(el==p)
{
continue;
}
if(sz[el]>maxx)
{
maxx=sz[el];
to=el;
}
}
if(maxx>all/2)
{
return find(to,i,all);
}
return i;
}
void dfs2(long long i,long long p,long long dist,long long br)
{
if(dist>k)
{
return;
}
if(cnt.find(dist)!=cnt.end())
{
cnt[dist]=min(cnt[dist],br);
}
else
{
cnt[dist]=br;
}
for(auto [el,_]:edges[i])
{
if(el==p)
{
continue;
}
dfs2(el,i,dist+_,br+1);
}
}
long long ans=0;
void calc(long long i,long long p,long long dist,long long br)
{
if(dist>k)
{
return;
}
if(cnt.find(k-dist)!=cnt.end())
{
ans=min(cnt[k-dist]+br,ans);
}
for(auto [el,_]:edges[i])
{
if(el==p)
{
continue;
}
calc(el,i,dist+_,br+1);
}
}
void build(long long i,long long par)
{
dfs(i,i);
long long cent=find(i,i,sz[i]);
cnt.clear();
ans=INT_MAX;
cnt[0]=0;
for(auto [el,_]:edges[cent])
{
calc(el,cent,_,1);
dfs2(el,cent,_,1);
}
trueans=min(trueans,ans);
if(par==-1)
{
p[cent]=cent;
}
else
{
p[cent]=par;
}
for(auto [el,_]:edges[cent])
{
edges[el].erase({cent,_});
build(el,cent);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
trueans=INT_MAX;
for(int i=0;i<n-1;i++)
{
edges[H[i][0]].insert({H[i][1],L[i]});
edges[H[i][1]].insert({H[i][0],L[i]});
}
build(0,-1);
if(trueans==INT_MAX) return -1;
return trueans;
}
