#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);
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<int> dn(n), sz(n);
vector<vector<int>> dd(n), ddis(n);
auto get_sz = [&](auto&& get_sz, int u, int p, int dep, int64_t dis, int f) -> void{
sz[u] = 0;
if(f){
dd[u].push_back(dep);
ddis[u].push_back(dis);
}
for(auto [x, w] : adj[u]){
if(x == p or dn[x]) continue;
get_sz(get_sz, x, u, dep + 1, dis + w, f);
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, 0, 0, 0);
int nds = sz[ctd];
ctd = getc(getc, ctd, -1, nds);
get_sz(get_sz, ctd, -1, 0, 0, 1);
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;
// for(auto x : dd){
// cout << x.size() << '\n';
// }
// exit(0);
auto solve = [&](auto&& solve, int u, int p) -> void{
mp[u][0] = 0;
// cerr << u << " " << p << '\n';
for(auto x : ntr[u]){
if(x == p) continue;
solve(solve, x, u);
for(auto z : all[x]){
// cerr << ddis[z].size()
int dist = ddis[z].back();
int cost = dd[z].back();
if(mp[u].count(k - dist)){
ans = min(ans, mp[u][k - dist] + cost);
}
}
for(auto z : all[x]){
int dist = ddis[z].back();
int cost = dd[z].back();
ddis[z].pop_back();
dd[z].pop_back();
if(!mp[u].count(dist)) mp[u][dist] = cost;
mp[u][dist] = min(mp[u][dist], cost);
all[u].push_back(z);
}
all[x].clear();
}
dd[u].pop_back();
ddis[u].pop_back();
all[u].push_back(u);
};
solve(solve, root, -1);
return ans > n ? -1 : ans;
}
