#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAX = 2*1e5+5;
vector< pair<int,int> > adj[MAX];
map< int,int > mp[MAX];
int da[MAX], dq[MAX], ans, k;
void merge(int p, int f, int w){
if(sz(mp[p]) >= sz(mp[f])){
//Conta
for(auto it : mp[f]){
int d = it.fi + da[f] + w;
if(mp[p].find(k - d - da[p]) != mp[p].end()) ans = min(ans, mp[p][k-d-da[p]]+dq[p] +it.sc+dq[f] +1);
}
//Adiciona
for(auto it : mp[f]){
int id = it.fi + da[f] + w - da[p];
if( mp[p].find(id) == mp[p].end())mp[p][id] = it.sc+dq[f] +1 -dq[p];
else mp[p][id] = min(mp[p][id]+dq[p], it.sc+dq[f] +1) - dq[p];
}
mp[f].clear();
}else{
//Conta
for(auto it : mp[p]){
int d = it.fi + da[p] + w;
if(mp[f].find(k - d - da[f]) != mp[f].end()) ans = min(ans, mp[f][k-d-da[f]]+dq[f] +it.sc+dq[p] +1);
}
//Adiciona
da[f] += w; dq[f]++;
for(auto it : mp[p]){
int id = it.fi + da[p] - da[f];
if( mp[f].find(id) == mp[f].end())mp[f][id] = it.sc+dq[p] - dq[f];
else mp[f][id] = min(mp[f][id]+dq[f], it.sc+dq[p]) - dq[f];
}
mp[p].clear();
swap(mp[p],mp[f]);
swap(da[p],da[f]);
swap(dq[p],dq[f]);
}
}
void dfs(int s, int p){
mp[s][0] = 0;
for(int i = 0; i < sz(adj[s]); i++){
int viz = adj[s][i].fi, w = adj[s][i].sc;
if(viz != p){
dfs(viz,s);
merge(s,viz,w);
}
}
}
int best_path(int n, int K, int h[][2], int l[]){
for(int i = 0; i < n-1; i++){
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
ans = n+1; k = K;
dfs(0,-1);
if(ans == n+1)ans = -1;
return ans;
}
