#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define int long long
#define INF 1e18
const int MAXN = 200005;
const int MAXK = 1000005;
struct Edge {
int to, len;
};
vector<Edge> adj[MAXN];
int sz[MAXN], deleted[MAXN];
int min_edges[MAXK]; // min_edges[d] - мин. ребер для пути длиной d
vector<int> changed_indices;
int ans = INF;
int current_k;
// Считаем размеры поддеревьев
void get_sz(int v, int p) {
sz[v] = 1;
for (auto& edge : adj[v]) {
if (edge.to != p && !deleted[edge.to]) {
get_sz(edge.to, v);
sz[v] += sz[edge.to];
}
}
}
// Ищем центроид
int get_centroid(int v, int p, int n) {
for (auto& edge : adj[v]) {
if (edge.to != p && !deleted[edge.to] && sz[edge.to] > n / 2) {
return get_centroid(edge.to, v, n);
}
}
return v;
}
// Собираем пути из текущего поддерева
void get_paths(int v, int p, int depth, int dist, vector<pair<int, int>>& paths) {
if (dist > current_k) return;
paths.pb({dist, depth});
for (auto& edge : adj[v]) {
if (edge.to != p && !deleted[edge.to]) {
get_paths(edge.to, v, depth + 1, dist + edge.len, paths);
}
}
}
void decompose(int v) {
get_sz(v, -1);
int centroid = get_centroid(v, -1, sz[v]);
deleted[centroid] = 1;
changed_indices.clear();
min_edges[0] = 0;
changed_indices.pb(0);
for (auto& edge : adj[centroid]) {
if (!deleted[edge.to]) {
vector<pair<int, int>> paths;
get_paths(edge.to, centroid, 1, edge.len, paths);
// 1. Проверяем пути, проходящие через центроид
for (auto& p : paths) {
if (current_k >= p.first) {
ans = min(ans, p.second + min_edges[current_k - p.first]);
}
}
// 2. Обновляем min_edges для следующих веток
for (auto& p : paths) {
if (p.first <= current_k) {
if (min_edges[p.first] == -1 || p.second < min_edges[p.first]) {
if (min_edges[p.first] == INF) changed_indices.pb(p.first);
min_edges[p.first] = p.second;
}
}
}
}
}
// Очистка min_edges для следующего центроида (эффективнее, чем memset)
for (int idx : changed_indices) min_edges[idx] = INF;
for (auto& edge : adj[centroid]) {
if (!deleted[edge.to]) {
decompose(edge.to);
}
}
}
// Основная функция по условию [cite: 14]
signed best_path(signed N, signed K, signed H[][2], signed L[]) {
current_k = K;
ans = INF;
for (int i = 0; i < N; i++) {
adj[i].clear();
deleted[i] = 0;
}
for (int i = 0; i <= K; i++) min_edges[i] = INF;
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
decompose(0);
if (ans >= INF) return -1; // Если путь не найден [cite: 21, 53]
return (signed)ans;
}
