#include <iostream>
#include <vector>
#include <cstring>
const int32_t MAX_N = 2e5;
const int32_t MAX_K = 1e6;
#ifdef LOCAL
#include "grader.cpp"
#endif
#ifndef LOCAL
#include "race.h"
#endif
struct Vertex {
bool solved;
int32_t subtree;
std::vector< std::pair< int32_t, int32_t > > v;
};
int32_t k, ans = -1, dists[MAX_K + 5];
Vertex g[MAX_N + 5];
void dfs_subtree(int32_t u, int32_t par) {
g[u].subtree = 1;
for(auto &e : g[u].v) {
auto v = e.first;
if(!g[v].solved && v != par) {
dfs_subtree(v, u);
g[u].subtree += g[v].subtree;
}
}
}
int32_t dfs_centroid(int32_t u, int32_t par, int32_t subtree) {
for(auto &e : g[u].v) {
auto v = e.first;
if(!g[v].solved && v != par && g[v].subtree > subtree / 2) {
return dfs_centroid(v, u, subtree);
}
}
return u;
}
void dfs_ans(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
if(d > k) {
return;
}
if(dists[k - d] != -1) {
if(ans == -1 || ans > cntEdges + dists[k - d]) {
ans = cntEdges + dists[k - d];
}
}
for(auto &e : g[u].v) {
auto v = e.first;
auto w = e.second;
if(!g[v].solved && v != par) {
dfs_ans(v, u, d + w, cntEdges + 1);
}
}
}
void dfs_add(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
if(d > k) {
return;
}
if(dists[d] == -1 || dists[d] > cntEdges) {
dists[d] = cntEdges;
}
for(auto &e : g[u].v) {
auto v = e.first;
auto w = e.second;
if(!g[v].solved && v != par) {
dfs_add(v, u, d + w, cntEdges + 1);
}
}
}
void dfs_clear(int32_t u, int32_t par, int32_t d) {
if(d > k) {
return;
}
dists[d] = -1;
for(auto &e : g[u].v) {
auto v = e.first;
auto w = e.second;
if(!g[v].solved && v != par) {
dfs_clear(v, u, d + w);
}
}
}
void solve(int32_t u) {
dfs_subtree(u, -1);
int32_t centroid = dfs_centroid(u, -1, g[u].subtree);
dists[0] = 0;
for(auto &e : g[centroid].v) {
auto v = e.first;
if(!g[v].solved) {
dfs_ans(v, centroid, e.second, 1);
dfs_add(v, centroid, e.second, 1);
}
}
dfs_clear(centroid, -1, 0);
g[centroid].solved = true;
for(auto &e : g[centroid].v) {
auto v = e.first;
if(!g[v].solved) {
solve(v);
}
}
}
int32_t best_path(int32_t n, int32_t _k, int32_t h[][2], int32_t l[]) {
k = _k;
for(int32_t i = 0; i < n - 1; i++) {
g[h[i][0]].v.push_back({ h[i][1], l[i] });
g[h[i][1]].v.push_back({ h[i][0], l[i] });
}
memset(dists, -1, sizeof(dists));
solve(1);
return ans;
}
