#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 1E6+16;
vector <pair <ll, ll> > adj[MAXN];
vector <char> used(MAXN, false);
vll sz(MAXN);
ll dfs_subsz (ll u, ll par) {
sz[u] = 1;
for (auto [v, w] : adj[u]) {
if (v == par) continue;
if (used[v]) continue;
sz[u] += dfs_subsz(v, u);
}
return sz[u];
}
ll dfs_ctd (ll u, ll par, ll n) {
for (auto [v, w] : adj[u]) {
if (v == par) continue;
if (used[v]) continue;
if (sz[v] > n/2) return dfs_ctd(v, u, n);
}
return u;
}
vll freq(MAXN, MAXN);
vll vis(MAXN, 0);
ll timer = 1;
void sett (ll dis, ll dep) {
if (vis[dis] != timer) { freq[dis] = MAXN; vis[dis] = timer; }
freq[dis] = min(freq[dis], dep);
}
ll get (ll dis) {
if (0 <= dis && dis < MAXN-8 && vis[dis] == timer) return freq[dis];
return MAXN;
}
ll k;
ll ans = MAXN;
void dfs_calc (ll u, ll par, ll dis, ll dep) {
if (dis > k) return;
ans = min(ans, get(k-dis)+dep);
for (auto [v, w] : adj[u]) {
if (v == par) continue;
if (used[v]) continue;
dfs_calc(v, u, dis+w, dep+1);
}
}
void dfs_dis (ll u, ll par, ll dis, ll dep) {
if (dis > k) return;
cerr << dis << ' ' << dep << " on " << u+1 << '\n';
sett(dis, dep);
for (auto [v, w] : adj[u]) {
if (v == par) continue;
if (used[v]) continue;
dfs_dis(v, u, dis+w, dep+1);
}
}
void solve (ll u) {
ll n = dfs_subsz(u, u);
ll ctd = dfs_ctd(u, u, n);
used[ctd] = true;
timer++;
sett(0, 0);
for (auto [v, w] : adj[ctd]) {
if (used[v]) continue;
dfs_calc(v, ctd, 0, 0);
dfs_dis(v, ctd, 0, 0);
}
for (auto [v, w] : adj[ctd]) {
if (used[v]) continue;
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
ll n = N;
k = K;
for (ll i = 0; i < n-1; i++) {
ll u = H[i][0], v = H[i][1];
ll w = L[i];
u--; v--;
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
solve(0);
return ans;
}
