#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
ll n, k;
ll sortsz(ll u, ll p){
ll sz=0;
ll mx=0;
for (auto &i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
ll ret = sortsz(v, u);
sz+=ret;
if (ret>mx){
swap(A[u][0], i);
mx=ret;
}
}
return sz;
}
void dfs(ll u, ll p, map<ll, ll> &len, ll &mn, ll addx, ll addy){
bool first=1;
map<ll, ll> nw;
for (auto i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
if (first){
dfs(v, u, len, mn, addx+e[i].ff, addy+1);
if (len.count(k+addx)){
mn = min(mn, len[k+addx]-addy);
}
first=0;
}else{
dfs(v, u, nw, mn, e[i].ff, 1);
for (auto [length, tim]:nw){
if (length==k){
mn=min(mn, tim);
}
// cout << "check: " << length << "-" << tim << " to " << addx << ln;
if (len.count(addx+(k-length)) and k-length>=0){
mn=min(mn, len[addx+(k-length)]-addy+tim);
}
}
for (auto [length, tim]:nw){
if (len.count(addx+length)){
len[length+addx] = min(tim+addy, len[length+addx]);
}else{
len[length+addx] = tim+addy;
}
}
nw.clear();
}
}
if (u!=p){
if (len.count(addx)){
len[addx]=min(len[addx], addy);
}else{
len[addx]=addy;
}
}
// cout << u << ": ";
// for (auto ch:len){
// cout << ch.ff << "-" << ch.ss << " ";
// }
// cout << ln;
}
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]}};
}
sortsz(0, 0);
ll mn = 2e18;
map<ll, ll> length;
dfs(0, 0, length, mn, 0, 0);
// for (auto ch:length){
// cout << ch.ff << "-" << ch.ss << ln;
// }
return (mn==2e18?-1:mn);
}
