#include "race.h"
#include <bits/stdc++.h>
template <class Fun> class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args> decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
struct Edge {
int u, v, w;
Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
int other(int x) const {
//khong mot ai ngoai em
return x ^ u ^ v;
}
};
int best_path(int n, int k, int H[][2], int L[]) {
std::vector <Edge> edges; edges.reserve(n - 1);
std::vector <std::vector <int>> g(n);
for (int i = 0; i < n - 1; i += 1) {
int u = H[i][0], v = H[i][1], w = L[i];
g[u].push_back(edges.size());
g[v].push_back(edges.size());
edges.emplace_back(u, v, w);
}
int ans = n + 1;
std::vector <int> was(n), siz(n), lvl(n), dist(n);
auto decompose = y_combinator([&] (auto decompose, int u) -> void {
int sz = y_combinator([&] (auto dfs, int u, int p) -> int {
int sz = 1;
for (int id : g[u]) {
int v = edges[id].other(u);
if (v == p or was[v])
continue;
sz += dfs(v, u);
}
return siz[u] = sz;
}) (u, u);
auto centroid = y_combinator([&] (auto centroid, int u, int p) -> int {
for (int id : g[u]) {
int v = edges[id].other(u);
if (v == p or was[v])
continue;
if (siz[v] > sz / 2)
return centroid(v, u);
}
return u;
});
std::unordered_map <int, int> maps;
auto chmin = [&] (int p, int x) -> void {
auto it = maps.emplace(p, x);
if (not it.second) {
it.first->second = std::min(it.first->second, x);
}
};
auto query = [&] (int p) -> int {
auto it = maps.find(p);
if (it == maps.end())
return n + 1;
return it->second;
};
int c = centroid(u, u);
lvl[c] = 0;
dist[c] = 0;
auto upd = y_combinator([&] (auto dfs, int u, int p) -> void {
for (int id : g[u]) {
int v = edges[id].other(u);
if (v == p or was[v])
continue;
if (dist[v] <= k) {
dfs(v, u);
chmin(dist[v], lvl[v]);
}
}
});
auto get = y_combinator([&] (auto dfs, int u, int p) -> void {
for (int id : g[u]) {
int v = edges[id].other(u);
if (v == p or was[v])
continue;
lvl[v] = lvl[u] + 1;
dist[v] = dist[u] + edges[id].w;
if (dist[v] <= k) {
dfs(v, u);
ans = std::min(ans, lvl[v] + query(k - dist[v]));
}
}
});
for (int id : g[c]) {
int x = edges[id].other(c);
if (was[x])
continue;
get(x, c);
upd(x, c);
}
was[c] = 1;
ans = std::min(ans, query(k));
for (int id : g[c]) {
int x = edges[id].other(c);
if (was[x])
continue;
decompose(x);
}
});
decompose(0);
return ans == n + 1 ? -1 : ans;
}
#ifdef ILOVELAMTER
int main(void) {
return 0;
}
#endif // ILOVELAMTER
