#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using pii = pair<int, int>;
#define x first
#define y second
const int N = 200005;
int n, k, res = N;
vector<pii> e[N];
struct SET{
set<pii> s;
pii ofs;
SET(): ofs(0, 0) { s.emplace(0, 0); }
};
SET *f(int x, int y){
if(x && e[x].size() == 1) return new SET();
vector<SET*> v;
SET* mx = NULL;
for(pii i : e[x]){
if(i.x == y) continue;
v.push_back(f(i.x, x));
v.back()->ofs.x += i.y;
v.back()->ofs.y++;
if(!mx || mx->s.size() < v.back()->s.size()) mx = v.back();
}
for(SET* i : v){
if(i == mx) continue;
for(pii j : i->s){
auto it = mx->s.lower_bound(pii(k - (j.x + i->ofs.x) - mx->ofs.x, -N));
if(it != mx->s.end() && it->x + mx->ofs.x + j.x + i->ofs.x == k)
res = min(res, it->y + mx->ofs.y + j.y + i->ofs.y);
}
for(pii j : i->s){
pii cur(j.x + i->ofs.x - mx->ofs.x, j.y + i->ofs.y - mx->ofs.y);
auto it = mx->s.lower_bound(pii(cur.x, -N));
if(it != mx->s.end() && it->x == cur.x){
if(it->y <= cur.y) continue;
if(it->y > cur.y) mx->s.erase(it);
}
mx->s.insert(cur);
}
}
set<pii> t;
while(!mx->s.empty() && mx->s.rbegin()->x + mx->ofs.x > k) mx->s.erase(*mx->s.rbegin());
mx->s.emplace(-mx->ofs.x, -mx->ofs.y);
auto it = mx->s.lower_bound(pii(k - mx->ofs.x, -N));
if(it != mx->s.end() && it->x + mx->ofs.x == k) res = min(res, it->y + mx->ofs.y);
return mx;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for(int i = 0; i < n-1; i++){
e[H[i][0]].emplace_back(H[i][1], L[i]);
e[H[i][1]].emplace_back(H[i][0], L[i]);
}
f(0, -1);
return (res == ::N ? -1 : res);
}
