#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef evenvalue
#include "debug.h"
#else
#define debug(...)
#endif
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
int best_path(const int n, const int k, int H[][2], int L[]) {
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++) {
const int x = H[i][0];
const int y = H[i][1];
const int w = L[i];
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
}
vector<int> sz(n);
vector<bool> decomposed(n);
function<int(int, int)> subtree_size = [&](const int x, const int p) {
sz[x] = 1;
for (const auto [y, w] : g[x]) {
if (decomposed[y] or y == p) continue;
sz[x] += subtree_size(y, x);
}
return sz[x];
};
function<int(int, int, int)> centroid = [&](const int x, const int p, const int size) {
int c = x;
for (const auto [y, w] : g[x]) {
if (decomposed[y] or y == p) continue;
if (2 * sz[y] < size) continue;
c = centroid(y, x, size);
break;
}
return c;
};
int ans = kInf;
map<int64, int> path;
function<void(int, int, int64, int)> upd_ans = [&](const int x, const int p, const int64 cost, const int d) {
if (path.count(k - cost)) {
ans = min(ans, path.at(k - cost) + d);
}
for (const auto [y, w] : g[x]) {
if (decomposed[y] or y == p) continue;
upd_ans(y, x, cost + w, d + 1);
}
};
function<void(int, int, int64, int)> upd_path = [&](const int x, const int p, const int64 cost, const int d) {
path.try_emplace(cost, d);
path[cost] = min(path[cost], d);
for (const auto [y, w] : g[x]) {
if (decomposed[y] or y == p) continue;
upd_path(y, x, cost + w, d + 1);
}
};
function<void(int)> decompose = [&](int x) {
x = centroid(x, -1, subtree_size(x, -1));
decomposed[x] = true;
path.clear();
path[0] = 0;
for (const auto [y, w] : g[x]) {
if (decomposed[y]) continue;
upd_ans(y, x, w, 1);
upd_path(y, x, w, 1);
}
for (const auto [y, w] : g[x]) {
if (decomposed[y]) continue;
decompose(y);
}
};
decompose(0);
return (ans == kInf ? -1 : ans);
}
