#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;
vector<pair<int, int>> adj[MAXN];
int sz[MAXN], deleted[MAXN];
int min_depth[MAXK]; // min_depth[d] - d masofaga yetish uchun minimal yo'llar soni
int ans = INF;
int N, K;
// Daraxt o'lchamini hisoblash
int get_sz(int u, int p) {
sz[u] = 1;
for (auto& edge : adj[u]) {
if (edge.first != p && !deleted[edge.first])
sz[u] += get_sz(edge.first, u);
}
return sz[u];
}
// Sentroidni topish
int get_centroid(int u, int p, int total) {
for (auto& edge : adj[u]) {
if (edge.first != p && !deleted[edge.first] && sz[edge.first] > total / 2)
return get_centroid(edge.first, u, total);
}
return u;
}
vector<pair<int, int>> current_paths;
// Sentroiddan chiquvchi yo'llarni yig'ish
void get_paths(int u, int p, int d, int dep) {
if (d > K) return;
current_paths.push_back({d, dep});
// K - d masofadagi eng yaxshi yo'lni tekshirish
if (min_depth[K - d] != INF) {
ans = min(ans, dep + min_depth[K - d]);
}
for (auto& edge : adj[u]) {
if (edge.first != p && !deleted[edge.first])
get_paths(edge.first, u, d + edge.second, dep + 1);
}
}
void decompose(int u) {
int centroid = get_centroid(u, -1, get_sz(u, -1));
deleted[centroid] = 1;
min_depth[0] = 0;
vector<int> updated_indices;
updated_indices.push_back(0);
for (auto& edge : adj[centroid]) {
if (!deleted[edge.first]) {
current_paths.clear();
get_paths(edge.first, centroid, edge.second, 1);
for (auto& p : current_paths) {
min_depth[p.first] = min(min_depth[p.first], p.second);
updated_indices.push_back(p.first);
}
}
}
// min_depth massivini tozalash (keyingi sentroid uchun)
for (int idx : updated_indices) min_depth[idx] = INF;
for (auto& edge : adj[centroid]) {
if (!deleted[edge.first]) decompose(edge.first);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
N = n; K = k;
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]});
}
for (int i = 0; i <= K; i++) min_depth[i] = INF;
decompose(0);
return (ans == INF ? -1 : ans);
}
