#include "race.h"
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
int bestres=1e9;
vector<vector<pair<int,int> > > adj;
vector<pair<unordered_map<int,int>, int> > v;
void dfs(int x, int e, int dph, int K) {
for(auto el : adj[x]) {
int b = el.first, w = el.second;
if(b==e)
continue;
dfs(b,x,dph+1,K);
v[b].first[-v[b].second]=dph+1;
v[b].second+=w;
if(v[b].first.size()>v[x].first.size()) {
swap(v[b],v[x]);
}
if(v[x].first.count(K-v[x].second)) {
bestres=min(bestres,v[x].first[K-v[x].second]-dph);
}
if(v[b].first.count(K-v[b].second)) {
bestres=min(bestres,v[b].first[K-v[b].second]-dph);
}
for(auto el : v[b].first) {
int realel = el.first+v[b].second;
if(v[x].first.count(K-realel-v[x].second)) {
bestres=min(bestres,v[x].first[K-realel-v[x].second]+el.second-2*dph);
}
}
for(auto el : v[b].first) {
int realel = el.first+v[b].second;
if(v[x].first.count(realel-v[x].second)) {
v[x].first[realel-v[x].second]=min(v[x].first[realel-v[x].second],el.second);
} else {
v[x].first[realel-v[x].second]=el.second;
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
v.resize(N);
adj.resize(N);
for(int i=0;i<N-1;i++) {
adj[H[i][0]].push_back(mp(H[i][1],L[i]));
adj[H[i][1]].push_back(mp(H[i][0],L[i]));
}
dfs(0,0,0,K);
if(bestres==1e9)
return -1;
return bestres;
}
