#include <bits/stdc++.h>
using namespace std;
// Chữ ký: H là mảng (N-1) x 2, L là mảng (N-1).
// Trả về minimum number of highways, hoặc -1 nếu không tồn tại.
int best_path(int N, int K, int H[][2], int L[]) {
if (N <= 1) return -1;
int n = N;
int k = K;
vector<vector<pair<int,int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> cnt(n, 0);
vector<char> del(n, 0);
int ans = INT_MAX;
// DFS để đếm kích thước subtree
function<void(int,int)> dfs_cnt = [&](int u, int p) {
cnt[u] = 1;
for (auto &e : adj[u]) {
int v = e.first;
if (v == p || del[v]) continue;
dfs_cnt(v, u);
cnt[u] += cnt[v];
}
};
// Tìm centroid của cây có root u, kích thước sz = cnt[root]
function<int(int,int,int)> find_centroid = [&](int u, int p, int sz) -> int {
for (auto &e : adj[u]) {
int v = e.first;
if (v == p || del[v]) continue;
if (cnt[v] > sz / 2) return find_centroid(v, u, sz);
}
return u;
};
// DFS thu thập (distance, number_of_highways) từ một nhánh
function<void(int,int,int,int,vector<pair<int,int>>&)> dfs_solve =
[&](int u, int p, int dist, int highways, vector<pair<int,int>> &vec) {
if (dist > k) return; // không cần tiếp tục
vec.push_back({dist, highways});
for (auto &e : adj[u]) {
int v = e.first, w = e.second;
if (v == p || del[v]) continue;
dfs_solve(v, u, dist + w, highways + 1, vec);
}
};
// Hàm đệ quy centroid-decomposition
function<void(int)> solve = [&](int start) {
dfs_cnt(start, -1);
int centroid = find_centroid(start, -1, cnt[start]);
del[centroid] = 1;
// mp lưu map: distance -> min highways để đạt distance từ centroid qua các nhánh đã xử lý
unordered_map<int,int> mp;
mp.reserve(256);
mp[0] = 0; // từ centroid đến chính nó: distance 0, highways 0
for (auto &e : adj[centroid]) {
int v = e.first, w = e.second;
if (del[v]) continue;
vector<pair<int,int>> vec;
dfs_solve(v, centroid, w, 1, vec);
// 1) kiểm tra kết hợp vec với các khoảng đã lưu trong mp (không dùng vec hiện tại để tránh ghép trong cùng 1 nhánh)
for (auto &pr : vec) {
int dis = pr.first, num = pr.second;
auto it = mp.find(k - dis);
if (it != mp.end()) {
ans = min(ans, it->second + num);
}
}
// 2) cập nhật mp bằng vec (sau khi kiểm tra)
for (auto &pr : vec) {
int dis = pr.first, num = pr.second;
auto it = mp.find(dis);
if (it == mp.end()) mp[dis] = num;
else if (num < it->second) it->second = num;
}
}
// tiếp tục với các thành phần con
for (auto &e : adj[centroid]) {
int v = e.first;
if (!del[v]) solve(v);
}
};
solve(0);
if (ans == INT_MAX) return -1;
return ans;
}
