#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXK = 1e6 +5, MAXN = 2e5+ 5;
vector<pii> v[MAXN];
vector<int> limpa;
int dp[MAXK], vis[MAXN], sz[MAXN], ans = MAXK, k;
int subtree(int node, int pai = 0) {
sz[node] = 1;
for (pii x : v[node]) {
if (!vis[x.first] && x.first != pai) {
sz[node] += subtree(x.first, node);
}
}
return sz[node];
}
int centroid(int node, int desired, int pai = 0) {
for (pii x : v[node]) {
if (!vis[x.first] && x.first != pai && sz[x.first] > desired) {
return centroid(x.first, desired, node);
}
}
return node;
}
void calcDP(int node, int pai, bool filling, int dep, int dist) {
if (dist > k) return;
if (filling) {
dp[dist] = min(dp[dist], dep);
if (dist)
limpa.push_back(dist);
}
else {
ans = min(ans, dep + dp[k - dist]);
}
for (pii x : v[node]) {
if (x.first != pai && !vis[x.first]) {
calcDP(x.first, node, filling, dep + 1, dist + x.second);
}
}
}
void solve(int node) {
int c = centroid(node, subtree(node) / 2);
vis[c] = true;
for(int i = 0; i < 2; i++) {
// do it once normally and then again reversed
for (pii x : v[c]) {
if (!vis[x.first]) {
calcDP(x.first, c, false, 1, x.second);
calcDP(x.first, c, true, 1, x.second);
}
}
for (int x : limpa) dp[x] = MAXK;
reverse(v[c].begin(), v[c].end());
}
for (pii x : v[c]) {
if (!vis[x.first]) {
solve(x.first);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N - 1; i++) {
v[H[i][0]].emplace_back(H[i][1], L[i]);
v[H[i][1]].emplace_back(H[i][0], L[i]);
}
for (int i = 1; i < MAXK; i++) dp[i] = MAXK;
solve(1);
return (ans == MAXK ? -1 : ans);
return N;
}
