#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
template <class F>
struct y_combinator_result {
F f;
template <class T>
explicit y_combinator_result(T &&f_) : f(std::forward<T>(f_)) {}
template <class... Args>
decltype(auto) operator()(Args &&...args) {
return f(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class F>
decltype(auto) y_combinator(F &&f) {
return y_combinator_result<std::decay_t<F>>(std::forward<F>(f));
}
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
g[h[i][0]].emplace_back(i);
g[h[i][1]].emplace_back(i);
}
int ans = n;
vector<int> depth(n);
vector<long long> dist(n);
vector<map<long long, int>> a(n);
y_combinator([&](auto dfs, int v, int p) -> void {
vector<int> c;
for (int id : g[v]) {
int to = v ^ h[id][0] ^ h[id][1];
if (to == p) {
continue;
}
c.emplace_back(to);
depth[to] = depth[v] + 1;
dist[to] = dist[v] + l[id];
dfs(to, v);
long long t = dist[v] + k;
if (a[to].count(t)) {
ans = min(ans, a[to][t] - depth[v]);
}
}
if (c.empty()) {
a[v][dist[v]] = depth[v];
return;
}
sort(c.begin(), c.end(), [&](int i, int j) {
return a[i].size() > a[j].size();
});
swap(a[v], a[c[0]]);
a[v][dist[v]] = depth[v];
for (int i = 1; i < (int) c.size(); i++) {
for (auto q : a[c[i]]) {
long long t = 2 * dist[v] - q.first + k;
if (a[v].count(t)) {
ans = min(ans, a[v][t] + q.second - 2 * depth[v]);
}
}
for (auto q : a[c[i]]) {
if (!a[v].count(q.first)) {
a[v][q.first] = n;
}
a[v][q.first] = min(a[v][q.first], q.second);
}
}
})(0, -1);
if (ans == n) {
ans = -1;
}
return ans;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
#endif
