#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 200005;
const int K_MAX = 1000005;
const int INF = 1e9;
vector<pair<int, int>> adj[N_MAX];
int sz[N_MAX], heavy[N_MAX];
int min_edges[K_MAX]; // Mảng toàn cục thay cho unordered_map để đạt O(1)
int ans, K_val;
bool is_heavy[N_MAX];
// Bước 1: Tìm con nặng (Heavy Child)
void get_sz(int u, int p) {
sz[u] = 1;
heavy[u] = -1;
int max_sz = 0;
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p) {
get_sz(v, u);
sz[u] += sz[v];
if (sz[v] > max_sz) {
max_sz = sz[v];
heavy[u] = v;
}
}
}
}
// Bước 2: Hàm cập nhật và kiểm tra (thay cho việc duyệt map)
// base_d và base_c là khoảng cách và số cạnh tính từ node gốc của Sack
void update(int u, int p, long long d, int c, bool fill, long long base_d, int base_c) {
long long dist = d - base_d;
if (dist > K_val) return;
if (fill) {
min_edges[dist] = min(min_edges[dist], c - base_c);
} else {
if (min_edges[K_val - dist] != INF) {
ans = min(ans, (c - base_c) + min_edges[K_val - dist]);
}
}
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && !is_heavy[v]) {
update(v, u, d + edge.second, c + 1, fill, base_d, base_c);
}
}
}
// Xóa dữ liệu mảng toàn cục sau khi xong nhánh nhẹ
void clear_data(int u, int p, long long d, long long base_d) {
long long dist = d - base_d;
if (dist > K_val) return;
min_edges[dist] = INF;
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && !is_heavy[v]) {
clear_data(v, u, d + edge.second, base_d);
}
}
}
// Bước 3: Hàm DFS Sack chính
void dfs_sack(int u, int p, long long d, int c, bool keep) {
// Duyệt các con nhẹ trước, xóa dữ liệu sau khi duyệt xong
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && v != heavy[u]) {
dfs_sack(v, u, d + edge.second, c + 1, false);
}
}
// Duyệt con nặng và giữ lại dữ liệu trong mảng min_edges
if (heavy[u] != -1) {
int hw = 0;
for(auto &e : adj[u]) if(e.first == heavy[u]) hw = e.second;
dfs_sack(heavy[u], u, d + hw, c + 1, true);
is_heavy[heavy[u]] = true;
}
// Kết hợp các nhánh nhẹ với nhánh nặng và chính node u
if (min_edges[K_val] != INF) ans = min(ans, min_edges[K_val]);
min_edges[0] = 0; // Gốc u có khoảng cách 0, số cạnh 0
for (auto &edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (v != p && v != heavy[u]) {
update(v, u, d + w, c + 1, false, d, c); // Kiểm tra kết quả trước
update(v, u, d + w, c + 1, true, d, c); // Sau đó mới đưa vào mảng
}
}
if (heavy[u] != -1) is_heavy[heavy[u]] = false;
if (!keep) {
clear_data(u, p, d, d);
min_edges[0] = INF;
}
}
int best_path(int N, int K, int H[][2], int L[]) {
// Reset dữ liệu
K_val = K;
ans = INF;
for (int i = 0; i < N; i++) {
adj[i].clear();
is_heavy[i] = false;
}
for (int i = 0; i <= K; i++) min_edges[i] = INF;
// Xây dựng đồ thị
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]});
}
get_sz(0, -1);
dfs_sack(0, -1, 0, 0, true);
return (ans >= INF) ? -1 : ans;
}
