#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 200000;
vector<pair<int,int>> g[MAXN + 5];
int num[MAXN + 5], del[MAXN + 5];
int tot, K;
int ans;
vector<int> min_edge;
vector<int> touched;
void calc_num(int u, int p) {
tot++;
num[u] = 1;
for (auto [v, w] : g[u]) {
if (v == p || del[v]) continue;
calc_num(v, u);
num[u] += num[v];
}
}
int find_cen(int u, int p) {
for (auto [v, w] : g[u]) {
if (v == p || del[v]) continue;
if (num[v] > tot / 2)
return find_cen(v, u);
}
return u;
}
void dfs_collect(int u, int p, int wei, int dep,
vector<pair<int,int>> &deps) {
deps.push_back({wei, dep});
for (auto [v, w] : g[u]) {
if (v == p || del[v]) continue;
dfs_collect(v, u, wei + w, dep + 1, deps);
}
}
void decompose(int u) {
tot = 0;
calc_num(u, -1);
int cen = find_cen(u, -1);
del[cen] = 1;
for (auto [v, w] : g[cen]) {
if (del[v]) continue;
vector<pair<int,int>> deps;
dfs_collect(v, cen, w, 1, deps);
for (auto [wei, dep] : deps) {
if (wei <= K && min_edge[K - wei] != INT_MAX) {
ans = min(ans, dep + min_edge[K - wei]);
}
}
for (auto [wei, dep] : deps) {
if (wei <= K) {
if (min_edge[wei] == INT_MAX)
touched.push_back(wei);
min_edge[wei] = min(min_edge[wei], dep);
}
}
}
for (int x : touched)
min_edge[x] = INT_MAX;
touched.clear();
for (auto [v, w] : g[cen]) {
if (!del[v])
decompose(v);
}
}
int best_path(int N, int K_input, int H[][2], int L[]) {
K = K_input;
ans = INT_MAX;
for (int i = 0; i < N; i++) {
g[i].clear();
del[i] = 0;
}
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});
}
min_edge.assign(K + 1, INT_MAX);
min_edge[0] = 0; // đường rỗng tại centroid
decompose(0);
return (ans == INT_MAX ? -1 : ans);
}
