#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;
vector<pair<int, int>> adj[MAXN];
int sz[MAXN], min_e[MAXK], ans;
bool vis[MAXN];
// Calculate subtree sizes
void get_sz(int u, int p) {
sz[u] = 1;
for (auto& edge : adj[u]) {
if (edge.first != p && !vis[edge.first]) {
get_sz(edge.first, u);
sz[u] += sz[edge.first];
}
}
}
// Find the centroid of the current component
int get_centroid(int u, int p, int total) {
for (auto& edge : adj[u]) {
if (edge.first != p && !vis[edge.first] && sz[edge.first] > total / 2)
return get_centroid(edge.first, u, total);
}
return u;
}
void solve(int u, int p, int d, int c, int K, vector<pair<int, int>>& nodes) {
if (d > K) return;
if (min_e[K - d] != INF) ans = min(ans, c + min_e[K - d]);
nodes.push_back({d, c});
for (auto& edge : adj[u]) {
if (edge.first != p && !vis[edge.first])
solve(edge.first, u, d + edge.second, c + 1, K, nodes);
}
}
void decompose(int u, int K) {
get_sz(u, -1);
int cen = get_centroid(u, -1, sz[u]);
vis[cen] = true;
vector<int> reset_list;
min_e[0] = 0;
reset_list.push_back(0);
for (auto& edge : adj[cen]) {
if (!vis[edge.first]) {
vector<pair<int, int>> nodes;
solve(edge.first, cen, edge.second, 1, K, nodes);
for (auto& it : nodes) {
if (it.first <= K) {
min_e[it.first] = min(min_e[it.first], it.second);
reset_list.push_back(it.first);
}
}
}
}
// Reset min_e for next centroid to keep O(N log N)
for (int d : reset_list) min_e[d] = INF;
for (auto& edge : adj[cen]) {
if (!vis[edge.first]) decompose(edge.first, K);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = INF;
for (int i = 0; i < N; i++) {
adj[i].clear();
vis[i] = false;
}
for (int i = 0; i < K + 1; i++) min_e[i] = INF;
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]});
}
decompose(0, K);
return (ans == INF) ? -1 : ans;
}
