#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first
#define s second
#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++) {
const auto &[u, v] = h[i];
adj[u].push_back({v, l[i]});
adj[v].push_back({u, l[i]});
}
vector<multiset<pair<int, int>>> paths(n);
ll ans = INT_MAX;
auto dfs = [&] (int node, int prev, auto &&dfs) -> void {
if (adj[node].size() == 1 && adj[node][0].f == prev) {
return;
}
for (auto [next, w] : adj[node]) {
if (next != prev) {
paths[node].insert({w, 1});
dfs(next, node, dfs);
if (paths[node].size() < paths[next].size()) swap(node, next);
for (auto i : paths[next]) {
ll t1 = i.f + w, t2 = i.s + 1;
auto it = paths[node].lower_bound({k - t1, -1});
if (t1 == k) {
ans = min(ans, t2);
} else if (it != paths[node].end() && it->first == k-t1) {
ans = min(ans, t2 + it->second);
}
auto it2 = paths[node].lower_bound({t1, -1});
if (it2 == paths[node].end() || it2->second >= t2) {
paths[node].erase(it);
paths[node].insert({t1, t2});
}
}
}
}
};
dfs(0, -1, dfs);
return ans;
}
