#include<bits/stdc++.h>
using namespace std;
#include "race.h"
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> adj(n);
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]);
}
vector<int> sub(n), del(n);
function<void(int, int)> get_sub = [&](int v, int p) {
sub[v] = 1;
for(auto &[u, w] : adj[v]) {
if(u != p && !del[u]) {
get_sub(u, v);
sub[v] += sub[u];
}
}
};
function<int(int, int, int)> get_centro = [&](int v, int p, int tree) {
bool is_centro = true;
if((tree - sub[v]) * 2 > tree)
is_centro = false;
for(auto &[u, w] : adj[v]) {
if(u != p && !del[u]) {
int r = get_centro(u, v, tree);
if(r != -1) return r;
if(sub[u] * 2 > tree)
is_centro = false;
}
}
if(is_centro) return v;
return -1;
};
int inf = 1e9, ans = inf;
vector<int> opt(k + 1, inf);
function<void(int, int, int, int, int)> get_ans = [&](int v, int p, int dep, int dst, int type) {
if(dst > k) return;
if(type == 1) ans = min(ans, dep + opt[k - dst]);
if(type == 2) opt[dst] = min(opt[dst], dep);
if(type == 3) opt[dst] = inf;
for(auto &[u, w] : adj[v])
if(u != p && !del[u])
get_ans(u, v, dep + 1, dst + w, type);
};
function<void(int)> decomp = [&](int v) {
get_sub(v, -1);
v = get_centro(v, -1, sub[v]);
opt[0] = 0;
for(auto &[u, w] : adj[v]) if(!del[u]) {
get_ans(u, v, 1, w, 1);
get_ans(u, v, 1, w, 2);
}
for(auto &[u, w] : adj[v]) if(!del[u])
get_ans(u, v, 1, w, 3);
del[v] = true;
for(auto &[u, w] : adj[v]) if(!del[u])
decomp(u);
};
decomp(0);
if(ans >= inf) ans = -1;
return ans;
}
