#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define ssize(x) (int)size(x)
template <class A, class B>
auto &operator<<(ostream &o, pair<A, B> p)
{
return o << '(' << p.first << ", " << p.second << ')';
}
template <class T>
auto operator<<(ostream &o, T x) -> decltype(x.end(), o)
{
o << '{';
int i = 0;
for (auto e : x)
o << (", ") + 2 * !i++ << e;
return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) \
{ \
}
#endif
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, int>>> graf(N);
for (int i = 0; i < N - 1; i++) {
int a = H[i][0], b = H[i][1], c = L[i];
graf[a].push_back({b, c});
graf[b].push_back({a, c});
}
int ans = N;
vector<int> subsz(N);
vector<bool> used(N);
function<void(int, int)> calc_sz = [&](int u, int p) {
subsz[u] = 1;
for (auto [to, _] : graf[u]) {
if (to == p || used[to]) continue;
calc_sz(to, u);
subsz[u] += subsz[to];
}
};
function<int(int, int, int)> calc_centro = [&](int u, int p, int need) {
for (auto [to, _] : graf[u]) {
if (to == p || used[to]) continue;
if (subsz[to] * 2 > need) return calc_centro(to, u, need);
}
return u;
};
vector<vector<pair<int, int>>> wek(K + 1);
vector<int> cos;
int pid = 0;
function<void(int, int, int, int, int)> gather = [&](int u, int p, int len, int path_id, int edges_count) {
if (len <= K) {
wek[len].push_back({edges_count, path_id});
cos.push_back(len);
}
else return; // xD?
for (auto [to, tlen] : graf[u]) {
if (to == p || used[to]) continue;
gather(to, u, len + tlen, path_id, edges_count + 1);
}
};
function<void(int)> rek = [&](int u) {
calc_sz(u, u);
u = calc_centro(u, u, subsz[u]);
for (auto [to, tlen] : graf[u]) {
if (used[to]) continue;
gather(to, u, tlen, ++pid, 1);
}
cos.push_back(0);
wek[0].push_back({0, -1});
sort(cos.begin(), cos.end());
cos.erase(unique(cos.begin(), cos.end()), cos.end());
for (auto x : cos) {
pair<int, int> min_1(N, 0);
for (auto d : wek[x])
min_1 = min(min_1, d);
pair<int, int> min_2(N, 0);
for (auto d : wek[x])
if (d.second != min_1.second) min_2 = min(min_2, d);
for (auto d : wek[K - x]) {
if (d.second != min_1.second) ans = min(ans, d.first + min_1.first);
if (d.second != min_2.second) ans = min(ans, d.first + min_2.first);
}
}
used[u] = 1;
for (auto x : cos)
wek[x].clear();
cos.clear();
for (auto [to, _] : graf[u]) {
if (used[to]) continue;
rek(to);
}
};
rek(0);
return (ans == N ? -1 : ans);
}
