#include "race.h"
#include <bits/stdc++.h>
using i64 = long long;
using i2 = std::array<int, 2>;
int best_path(int N, int K, int H[][2], int L[]) {
std::vector<std::vector<i2>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
std::vector<int> sz(N, 1), imp(N, -1), h(N);
std::vector<i64> d(N);
auto prep = [&](auto self, int v, int f) -> void {
for (auto [u, w] : adj[v]) {
if (u != f) {
h[u] = h[v] + 1;
d[u] = d[v] + w;
self(self, u, v);
sz[v] += sz[u];
if (imp[v] == -1 || sz[imp[v]] < sz[u]) {
imp[v] = u;
}
}
}
};
prep(prep, 0, 0);
std::vector<i64> t = d;
std::sort(t.begin(), t.end());
t.erase(std::unique(t.begin(), t.end()), t.end());
std::map<i64, int> key;
for (int i = 0; i < t.size(); i++) {
key[t[i]] = i;
}
auto cmp = [&h](int i, int j) {
return h[i] < h[j];
};
std::vector per((int) t.size(), std::set<int, decltype(cmp)> (cmp));
int ans = N;
auto add = [&](auto self, int v, int f) -> void {
per[key[d[v]]].insert(v);
for (auto [u, w] : adj[v]) {
if (u != f) {
self(self, u, v);
}
}
};
auto rem = [&](auto self, int v, int f) -> void {
per[key[d[v]]].erase(v);
for (auto [u, w] : adj[v]) {
if (u != f) {
self(self, u, v);
}
}
};
auto calc = [&](auto self, int v, int f, int r) -> void {
i64 req = K + 2 * d[r] - d[v];
if (key.contains(req) && !per[key[req]].empty()) {
int u = *per[key[req]].begin();
ans = std::min(ans, h[v] + h[u] - 2 * h[r]);
}
for (auto [u, w] : adj[v]) {
if (u != f) {
self(self, u, v, r);
}
}
};
auto sep = [&](int v) {
i64 req = K + d[v];
if (key.count(req) && !per[key[req]].empty()) {
int u = *per[key[req]].begin();
ans = std::min(ans, h[u] - h[v]);
}
per[key[d[v]]].insert(v);
};
auto dfs = [&](auto self, int v, int f) -> void {
for (auto [u, w] : adj[v]) {
if (u != f && u != imp[v]) {
self(self, u, v);
rem(rem, u, v);
}
}
if (imp[v] != -1) {
self(self, imp[v], v);
}
for (auto [u, w] : adj[v]) {
if (u != f && u != imp[v]) {
calc(calc, u, v, v);
add(add, u, v);
}
}
sep(v);
};
dfs(dfs, 0, 0);
if (ans == N) {
return -1;
} else {
return ans;
}
}
