#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
typedef long long int lol;
vector<vector<pair<int,int> > > g(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> del;
int ans=INT_MAX;
void dfssz(int u,int p=-1)
{
subsz[u]=1;
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
{
dfssz(ch.first,u);
subsz[u]+=subsz[ch.first];
}
}
}
int getcen(int u,int sz,int p=-1)
{
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
{
if(subsz[ch.first]>sz/2) return getcen(ch.first,sz,u);
}
}
return u;
}
void solve(int u,map<int,set<pair<int,int> > > &m,int len,int K,int dep,int z,int p)
{
for(auto ch:g[u])
{
if(ch.first==p) continue;
if(!del.test(ch.first))
{
if(len+ch.second<=K)
{
m[len+ch.second].emplace(1+dep,z);
solve(ch.first,m,len+ch.second,K,1+dep,z,u);
}
}
}
}
void centroid(int u,const int& K)
{
//find subtree sizes
dfssz(u);
//get centroid
int C=getcen(u,subsz[u]);
//solve
map<int,set<pair<int,int> > > m;
for(auto ch:g[C])
{
if(!del.test(ch.first))
{
if(ch.second<=K)
{
m[ch.second].emplace(1,ch.first);
solve(ch.first,m,ch.second,K,1,ch.first,C);
}
}
}
if(m.find(K)!=m.end())
{
ans=min(ans,m[K].begin()->first);
}
for(auto p:m)
{
if(m.find(K-p.first)!=m.end())
{
if(m[K-p.first].begin()->second==p.second.begin()->second)
{
if(m[K-p.first].size()>=2)
{
auto it=++(m[K-p.first].begin());
ans=min(ans,p.second.begin()->first+it->first);
}
}else
{
ans=min(ans,p.second.begin()->first+m[K-p.first].begin()->first);
}
}
}
//end
del.flip(C);
for(auto ch:g[C])
{
if(!del.test(ch.first)) centroid(ch.first,K);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N-1;i++)
{
int u=H[i][0],v=H[i][1];
g[u].emplace_back(v,L[i]);
g[v].emplace_back(u,L[i]);
}
centroid(0,K);
if(ans==INT_MAX) return -1;
else return ans;
}
