#include<iostream>
#include<vector>
#include<map>
#include<set>
#include"race.h"
typedef long long ll;
#define vec vector
using namespace std;
struct Edge {
ll to, w;
};
ll ans, k;
vec<vec<Edge> > adj;
vec<ll> deleted, ofLength, usedLengths, s;
void find_sizes(ll v, ll p = -1) {
s[v] = 1;
for (auto &e : adj[v])
if (!deleted[e.to] && e.to != p) {
find_sizes(e.to, v);
s[v] += s[e.to];
}
}
ll find_centroid(ll v, ll n, ll p = -1) {
for (auto &e : adj[v])
if (!deleted[e.to] && e.to != p && s[e.to] * 2 > n)
return find_centroid(e.to, n, v);
return v;
}
void use_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
for (auto &e : adj[v])
if (!deleted[e.to] && e.to != p)
use_dfs(e.to, dist + e.w, dist1 + 1, v);
if (dist > k) return;
ans = min(ans, ofLength[k - dist] + dist1);
if (dist == k)
ans = min(ans, dist1);
}
void apply_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
for (auto &e : adj[v])
if (!deleted[e.to] && e.to != p)
apply_dfs(e.to, dist + e.w, dist1 + 1, v);
if (dist > k) return;
ofLength[dist] = min(ofLength[dist], dist1);
usedLengths.push_back(dist);
}
void divide(ll v = 0) {
find_sizes(v);
ll cent = find_centroid(v, s[v]);
deleted[cent] = 1;
for (auto &e : adj[cent]) {
use_dfs(e.to, e.w);
apply_dfs(e.to, e.w);
}
for (auto &l : usedLengths)
ofLength[l] = 1e9;
usedLengths.clear();
for (auto &e : adj[cent])
if (!deleted[e.to])
divide(e.to);
}
// int main() {
// ll n;
// cin >> n >> k;
// adj.assign(n, {});
// deleted.assign(n, 0);
// s.resize(n);
// ofLength.assign(k + 1, 1e9);
// ans = 1e9;
// for (ll i = 0; i < n - 1; i++) {
// ll a, b, w;
// cin >> a >> b >> w;
// adj[a].push_back({b, w});
// adj[b].push_back({a, w});
// }
// divide();
// cout << (ans == 1e9 ? -1 : ans) << '\n';
// }
int best_path(int N, int K, int H[][2], int L[]) {
ll i;
k = K;
deleted.assign(N, 0);
adj.assign(N, {});
s.resize(N);
ofLength.assign(K + 1, 1e9);
ans = 1e9;
for (i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
divide();
return (ans == 1e9 ? -1 : ans);
}
