#include <bits/stdc++.h>
using namespace std;
static const int INF = 1e9;
int N, K;
vector<pair<int,int>> g[200005];
bool dead[200005];
int sz[200005];
int ans;
/* ---------- tính size ---------- */
void dfs_size(int u, int p) {
sz[u] = 1;
for (auto &e : g[u]) {
int v = e.first;
if (v == p || dead[v]) continue;
dfs_size(v, u);
sz[u] += sz[v];
}
}
/* ---------- tìm centroid ---------- */
int dfs_centroid(int u, int p, int tot) {
for (auto &e : g[u]) {
int v = e.first;
if (v == p || dead[v]) continue;
if (sz[v] * 2 > tot)
return dfs_centroid(v, u, tot);
}
return u;
}
/* ---------- thu thập (dist, edges) ---------- */
void dfs_collect(int u, int p, int dist, int edges,
vector<pair<int,int>> &vec) {
if (dist > K) return;
vec.push_back({dist, edges});
for (auto &e : g[u]) {
int v = e.first, w = e.second;
if (v == p || dead[v]) continue;
dfs_collect(v, u, dist + w, edges + 1, vec);
}
}
/* ---------- xử lý tại centroid ---------- */
void process(int c) {
unordered_map<int,int> best;
best.reserve(1024);
best[0] = 0;
for (auto &e : g[c]) {
int v = e.first, w = e.second;
if (dead[v]) continue;
vector<pair<int,int>> vec;
dfs_collect(v, c, w, 1, vec);
// query
for (auto &x : vec) {
int d = x.first, cnt = x.second;
if (best.count(K - d))
ans = min(ans, cnt + best[K - d]);
}
// merge (small to large)
for (auto &x : vec) {
int d = x.first, cnt = x.second;
if (!best.count(d))
best[d] = cnt;
else
best[d] = min(best[d], cnt);
}
}
}
/* ---------- centroid decomposition ---------- */
void decompose(int entry) {
dfs_size(entry, -1);
int c = dfs_centroid(entry, -1, sz[entry]);
dead[c] = true;
process(c);
for (auto &e : g[c]) {
int v = e.first;
if (!dead[v])
decompose(v);
}
}
/* ================================================= */
/* ================== API HÀM CHÍNH ================= */
/* ================================================= */
int best_path(int n, int k, int H[][2], int L[]) {
N = n;
K = k;
ans = INF;
for (int i = 0; i < N; i++) {
g[i].clear();
dead[i] = false;
}
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(0);
if (ans == INF) return -1;
return ans;
}
