#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int INF = 1e9;
int k;
vector<int> sz;
vector<bool> rem;
vector<vector<pair<int, int>>> adj;
void minSelf(int &x, int y) {
if(y < x) {
x = y;
}
}
void dfs(int u, int v = -1) {
sz[u] = 1;
for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
dfs(it.first, u);
sz[u] += sz[it.first];
}
}
int centroid(int desired, int u, int v = -1) {
for(const auto &it: adj[u]) if(it.first != v && !rem[it.first] && (sz[it.first] << 1) > desired) {
return centroid(desired, it.first, u);
}
return u;
}
map<int, int> mp;
void dfsUpdate(int u, int v, int dep, int cnt = 1) {
if(k >= dep) {
if(mp.count(dep) == 0) {
mp.emplace(dep, cnt);
} else {
minSelf(mp[dep], cnt);
}
for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
dfsUpdate(it.first, u, dep + it.second, cnt + 1);
}
}
}
int dfsQuery(int u, int v, int dep, int cnt = 1) {
int ans = INF;
if(k >= dep) {
if(mp.count(k - dep) > 0) {
minSelf(ans, cnt + mp[k - dep]);
}
for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
minSelf(ans, dfsQuery(it.first, u, dep + it.second, cnt + 1));
}
}
return ans;
}
void preorder(int u, int v, int dep, int cnt = 1) {
cout << u << " " << dep << " " << cnt << '\n';
for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
preorder(it.first, u, dep + it.second, cnt + 1);
}
}
int solve(int u = 0) {
dfs(u);
int c = centroid(sz[u], u);
int ans = INF;
for(const auto &it: adj[c]) if(!rem[it.first]) {
minSelf(ans, dfsQuery(it.first, c, it.second));
dfsUpdate(it.first, c, it.second);
}
if(mp.count(k) > 0) {
minSelf(ans, mp[k]);
}
rem[c] = 1;
mp.clear();
for(const auto &it: adj[c]) if(!rem[it.first]) {
minSelf(ans, solve(it.first));
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
adj = vector<vector<pair<int, int>>> (N);
for(int i = 0; i < N - 1; i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
sz = vector<int> (N);
rem = vector<bool> (N);
k = K;
int ans = solve();
if(ans == INF) {
return -1;
} else {
return ans;
}
}
