#include <bits/stdc++.h> using namespace std; static const int INF = 1e9; int best_path(int N, int K, int H[][2], int L[]) { vector<vector<pair<int,int> > > adj(N); for (int i = 0; i < N - 1; i++) { int u = H[i][0]; int v = H[i][1]; int w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } vector<int> sz(N); vector<bool> removed(N, false); int answer = INF; function<void(int,int)> dfs_size = [&](int u, int p) { sz[u] = 1; for (auto [v, w]: adj[u]) { if (v == p || removed[v]) continue; dfs_size(v, u); sz[u] += sz[v]; } }; function<int(int,int,int)> find_centroid = [&](int u, int p, int tot) { for (auto [v, w]: adj[u]) { if (v == p || removed[v]) continue; if (sz[v] > tot / 2) return find_centroid(v, u, tot); } return u; }; vector<pair<int,int> > paths; function<void(int,int,int,int)> dfs_paths = [&](int u, int p, int dist, int edges) { if (dist > K) return; paths.push_back({dist, edges}); for (auto [v, w]: adj[u]) { if (v == p || removed[v]) continue; dfs_paths(v, u, dist + w, edges + 1); } }; function<void(int)> decompose = [&](int entry) { dfs_size(entry, -1); int c = find_centroid(entry, -1, sz[entry]); removed[c] = true; unordered_map<int,int> best; best.reserve(sz[entry] * 2); best[0] = 0; for (auto [v, w]: adj[c]) { if (removed[v]) continue; paths.clear(); dfs_paths(v, c, w, 1); for (auto [d, e]: paths) { auto it = best.find(K - d); if (it != best.end()) { answer = min(answer, e + it->second); } } for (auto [d, e]: paths) { auto it = best.find(d); if (it == best.end() || it->second > e) { best[d] = e; } } } for (auto [v, w]: adj[c]) { if (!removed[v]) decompose(v); } }; decompose(0); return (answer == INF ? -1 : answer); }