#include "race.h"
#include <iostream>
#include <vector>
using namespace std;
const int MXN = 2e5 + 5, INF = 1e9 + 5;
vector<pair<int, int>> g[MXN];
int subtree_sz[MXN];
bool vis[MXN];
int N, K;
int ans = INF;
struct two_set {
pair<int, int> x, y;
two_set() { x = y = make_pair(INF, INF); }
void insert(int val, int node) {
if (val < y.first) y = make_pair(val, node);
if (x.first > y.first) swap(x, y);
}
int query(int exclude_node) {
if (x.second == exclude_node) return y.first;
return x.first;
}
void work(int u) {
if (x.second == u) x = make_pair(INF, INF);
else if (y.second == u) y = make_pair(INF, INF);
if (x.first > y.first) swap(x, y);
}
} mn_val[int(1e6) + 5];
int find_centroid(int u, int p, int nodes) {
if (p != -1) {
subtree_sz[p] -= subtree_sz[u];
subtree_sz[u] += subtree_sz[p];
}
for (const auto &[v, wt] : g[u])
if (v != p && !vis[v] && subtree_sz[v] * 2 > nodes)
return find_centroid(v, u, nodes);
return u;
}
vector<int> to_reset;
void calc_dist(int u, int p, int len, int depth, bool remove) {
if (len > K) return;
if (!remove) {
if (len <= K) mn_val[len].insert(depth, u);
to_reset.push_back(len);
} else {
if (len <= K) {
mn_val[len].work(u);
}
}
for (const auto &[v, wt] : g[u])
if (v != p && !vis[v]) calc_dist(v, u, len + wt, depth + 1, remove);
}
void calc_ans(int u, int p, int len, int depth) {
if (len > K) return;
if (len < K) ans = min(ans, depth + mn_val[K - len].query(u));
if (len == K) ans = min(ans, depth);
for (const auto &[v, wt] : g[u])
if (v != p && !vis[v]) calc_ans(v, u, len + wt, depth + 1);
}
void calc_sz(int u, int p) {
subtree_sz[u] = 1;
for (const auto &[v, wt] : g[u]) {
if (v == p) continue;
calc_sz(v, u);
subtree_sz[u] += subtree_sz[v];
}
}
void cd(int u) {
int centroid = find_centroid(u, -1, subtree_sz[u]);
vis[centroid] = true;
for (const auto &[v, wt] : g[centroid])
if (!vis[v]) calc_dist(v, centroid, wt, 1, false);
for (const auto &[v, wt] : g[centroid]) {
if (!vis[v]) {
calc_dist(v, centroid, wt, 1, true);
calc_ans(v, centroid, wt, 1);
calc_dist(v, centroid, wt, 1, false);
}
}
for (const auto &x : to_reset)
mn_val[x] = two_set();
to_reset.clear();
for (const auto &[v, wt] : g[centroid])
if (!vis[v]) cd(v);
}
int best_path(int _N, int _K, int _H[][2], int _L[]) {
N = _N, K = _K;
for (int i = 0; i < N - 1; i++) {
_H[i][0]++;
_H[i][1]++;
g[_H[i][0]].emplace_back(_H[i][1], _L[i]);
g[_H[i][1]].emplace_back(_H[i][0], _L[i]);
}
calc_sz(1, -1);
cd(1);
return (ans < INF ? ans : -1);
}
