#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int best_path(int n_, int k_, int H[][2], int L[]){
int n, k;
n = n_;
k = k_;
vector<vector<pair<int, int>>> adj(n);
vector<int64_t> d(n);
for(int i = 0; i < n - 1; i++){
int u, v, w;
u = H[i][0], v = H[i][1];
w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<vector<int>> jmp(20, vector(n, -1));
vector<int> dep(n), dis(n);
auto dfs = [&](int u, int p, auto&& self) -> void{
jmp[0][u] = p;
for(int i = 1; i < 20; i++){
if(jmp[i - 1][u] + 1) {
jmp[i][u] = jmp[i - 1][jmp[i - 1][u]];
}
}
for(auto [x, w] : adj[u]){
if(x == p) continue;
dep[x] = dep[u] + 1;
dis[x] = dis[u] + w;
self(x, u, self);
}
};
dfs(0, -1, dfs);
auto lca = [&](int u, int v){
if(dep[u] < dep[v]) swap(u, v); // make u deeper
int d = dep[u] - dep[v];
for(int i = 0; i < 20; i++){
if(d >> i & 1) u = jmp[i][u];
}
if(u == v) return u;
for(int i = 19; i >= 0; i--){
if(jmp[i][u] != jmp[i][v]) u = jmp[i][u], v = jmp[i][v];
}
return jmp[0][u];
};
auto get = [&](int u, int v){
return dis[u] + dis[v] - 2 * dis[lca(u, v)];
};
auto get1 = [&](int u, int v){
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
};
vector<int> dn(n), sz(n);
auto get_sz = [&](auto&& get_sz, int u, int p) -> void{
sz[u] = 0;
for(auto [x, w] : adj[u]){
if(x == p or dn[x]) continue;
get_sz(get_sz, x, u);
sz[u] += sz[x];
}
sz[u]++;
};
auto getc = [&](auto&& getc, int u, int p, int nds) -> int{
for(auto [x, w] : adj[u]){
if(x == p or dn[x]) continue;
if(sz[x] * 2 > nds){
return getc(getc, x, u, nds);
}
}
return u;
};
vector<vector<int>> ntr(n);
int root = -1;
auto cd = [&](auto&& cd, int ctd, int pr) -> void{
get_sz(get_sz, ctd, -1);
int nds = sz[ctd];
ctd = getc(getc, ctd, -1, nds);
if(pr != -1)
ntr[pr].push_back(ctd);
dn[ctd] = 1;
if(pr == -1) root = ctd;
for(auto [x, w] : adj[ctd]){
if(dn[x]) continue;
cd(cd, x, ctd);
}
};
cd(cd, 0, -1);
vector<vector<int>> all(n);
vector<map<int64_t, int>> mp(n);
int ans = 1e9;
auto solve = [&](auto&& solve, int u, int p) -> void{
mp[u][0] = 0;
for(auto x : ntr[u]){
if(x == p) continue;
solve(solve, x, u);
for(auto z : all[x]){
int dist = get(z, u);
if(mp[u].count(k - dist)){
ans = min(ans, mp[u][k - dist] + get1(u, z));
}
}
for(auto z : all[x]){
int dist = get(z, u);
int cost = get1(z, u);
if(!mp[u].count(dist)) mp[u][dist] = cost;
mp[u][dist] = min(mp[u][dist], cost);
}
all[x].clear();
}
all[u].push_back(u);
};
solve(solve, root, -1);
return (ans > n ? -1 : ans);
}
