#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
const int maxK = 1e6 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
int sz[maxN];
int best[maxK];
pair<int, int> dist[maxN];
int res;
int N, K;
void dfs1(int u, int p) {
sz[u] = 1;
for (auto e: adj[u]) {
int v = e.first;
if (!flag[v] && v != p) {
dfs1(v, u);
sz[u] += sz[v];
}
}
}
int cen(int r, int u, int p) {
for (auto e: adj[u]) {
int v = e.first;
if (!flag[v] && v != p && sz[v] * 2 > sz[r]) {
return cen(r, v, u);
}
}
return u;
}
void dfs2(int u, int p, int op) {
if (dist[u].second > K) {
return;
}
if (op == 1) {
res = min(res, dist[u].first + best[K - dist[u].second]);
}
if (op == 2) {
best[dist[u].second] = min(best[dist[u].second], dist[u].first);
}
if (op == 3) {
best[dist[u].second] = N;
}
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (!flag[v] && v != p) {
dist[v] = make_pair(dist[u].first + 1, dist[u].second + w);
dfs2(v, u, op);
}
}
}
void solve(int u) {
dfs1(u, -1);
u = cen(u, u, -1);
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (!flag[v]) {
dist[v] = make_pair(1, w);
dfs2(v, u, 1);
dfs2(v, u, 2);
}
}
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (!flag[v]) {
dist[v] = make_pair(1, w);
dfs2(v, u, 3);
}
}
flag[u] = true;
for (auto e: adj[u]) {
int v = e.first;
if (!flag[v]) {
solve(v);
}
}
}
int best_path(int _N, int _K, int H[][2], int L[]) {
N = _N;
K = _K;
best[0] = 0;
for (int i = 1; i <= K; i++) {
best[i] = N;
}
res = N;
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
solve(1);
if (res == N) {
return -1;
}
else {
return res;
}
}
