#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;
// Global state for Centroid Decomposition
vector<pair<int, int>> adj[MAXN];
int sz[MAXN], vis[MAXN];
int mn_ans;
int K_val;
// Lookup table for minimum edges for a given distance
int min_edges[MAXK];
// Rollback buffers to avoid O(K) memset
int rollback_list[MAXN];
int rollback_ptr = 0;
// Buffer for current subtree nodes
pair<int, int> subtree_nodes[MAXN];
int subtree_ptr = 0;
void get_size(int u, int p) {
sz[u] = 1;
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && !vis[v]) {
get_size(v, u);
sz[u] += sz[v];
}
}
}
int get_centroid(int u, int p, int total_n) {
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && !vis[v] && sz[v] > total_n / 2) {
return get_centroid(v, u, total_n);
}
}
return u;
}
void dfs_collect(int u, int p, int depth, int cost) {
if (cost > K_val) return;
subtree_nodes[subtree_ptr++] = {depth, cost};
for (auto &edge : adj[u]) {
int v = edge.first;
if (v != p && !vis[v]) {
dfs_collect(v, u, depth + 1, cost + edge.second);
}
}
}
void solve(int u) {
get_size(u, -1);
int cen = get_centroid(u, -1, sz[u]);
vis[cen] = 1;
rollback_ptr = 0;
min_edges[0] = 0;
rollback_list[rollback_ptr++] = 0;
for (auto &edge : adj[cen]) {
int v = edge.first;
if (vis[v]) continue;
subtree_ptr = 0;
dfs_collect(v, cen, 1, edge.second);
// Step 1: Query - Match current branch nodes against previous branches
for (int i = 0; i < subtree_ptr; i++) {
int d = subtree_nodes[i].second;
int e = subtree_nodes[i].first;
if (K_val >= d && min_edges[K_val - d] != INF) {
mn_ans = min(mn_ans, e + min_edges[K_val - d]);
}
}
// Step 2: Merge - Add current branch nodes to the lookup table
for (int i = 0; i < subtree_ptr; i++) {
int d = subtree_nodes[i].second;
int e = subtree_nodes[i].first;
if (d <= K_val) {
if (min_edges[d] == INF) rollback_list[rollback_ptr++] = d;
min_edges[d] = min(min_edges[d], e);
}
}
}
// Rollback distances used by this centroid
for (int i = 0; i < rollback_ptr; i++) {
min_edges[rollback_list[i]] = INF;
}
// Recurse to subtrees
for (auto &edge : adj[cen]) {
if (!vis[edge.first]) {
solve(edge.first);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
// Reset global state for each call [cite: 130, 131]
K_val = K;
mn_ans = INF;
rollback_ptr = 0;
subtree_ptr = 0;
for (int i = 0; i < N; i++) {
adj[i].clear();
vis[i] = 0;
sz[i] = 0;
}
// Using a loop for the large K array to ensure it is fully initialized
for (int i = 0; i < MAXK; i++) {
min_edges[i] = INF;
}
// Build the highways network [cite: 17, 18, 19]
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]});
}
solve(0);
// Return the minimum highways or -1 if no valid course exists [cite: 21]
return (mn_ans >= INF) ? -1 : mn_ans;
}
