#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll int
#define ff first
#define ss second
#define ln "\n"
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<bool> black;
vector<ll> sz;
set<pair<ll, ll>> levs, full;
ll n, k;
ll getsz(ll u, ll p){
sz[u]=1;
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
sz[u]+=getsz(v, u);
}
return sz[u];
}
void findcentroid(ll u, ll p, ll up, ll ¢r, ll wsz){
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
if (sz[v]>wsz/2) {findcentroid(v, u, up+1, centr, wsz); return;}
}
centr=u;
return;
}
void dfs(ll u, ll p, ll level, ll dep){
levs.insert({level, dep});
for (auto i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p or black[i]) continue;
dfs(v, u, level+e[i].ff, dep+1);
}
}
void cedfs(ll u, ll &mn, ll wsz){
levs.clear(); full.clear();
ll centr = -1;
findcentroid(u,u, 0, centr, wsz);
// assert(centr!=-1);
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
levs.clear();
dfs(v, u, e[i].ff, 1);
for (auto [length, tim]:levs){
auto it = full.lower_bound({k-length, -1});
if (!full.empty() and it!=full.end() and (*it).ff==k-length){
mn=min(mn, tim+(*it).ss);
}
if (length==k) {
mn=min(mn, tim);
}
}
// cout << ln;
for (auto [length, tim]:levs){
full.insert({length, tim});
}
}
for (auto i:A[u]){
if (black[i]) continue;
black[i]=1;
ll v = e[i].ss.ff^e[i].ss.ss^u;
cedfs(v, mn, getsz(v, v));
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N; k=K;
e.resize(N-1);
A.resize(N);
for (ll i=0; i<n-1; i++){
A[H[i][0]].push_back(i);
A[H[i][1]].push_back(i);
e[i] = {L[i], {H[i][0], H[i][1]}};
}
black.resize(N);
sz.resize(N);
ll mn = n+1;
cedfs(0, mn, getsz(0, 0));
return (mn==n+1?-1:mn);
}
