#include "race.h"
#include <vector>
#include <map>
using namespace std;
int K;
const int INF = 1e9;
vector<vector<pair<int, int>>> g;
vector<int> sz, vis;
int get_centroid(int root) {
auto sub_size = [&](auto sub_size, int x, int p) -> void {
sz[x] = 1;
for(auto [z, w]: g[x]) {
if(z != p && vis[z] == 0) {
sub_size(sub_size, z, x);
sz[x] += sz[z];
}
}
};
sub_size(sub_size, root, -1);
int n = sz[root];
auto dfs = [&](auto dfs, int x, int p) -> int {
for(auto [z, w]: g[x]) {
if(z != p && vis[z] == 0) {
if(2 * sz[z] > n) return dfs(dfs, z, x);
}
}
return x;
};
return dfs(dfs, root, -1);
}
int get(int c) {
c = get_centroid(c);
int ans = INF;
map<int, int> mp;
mp[0] = 0;
vector<pair<int, int>> collect;
auto dfs = [&](auto dfs, int x, int p, int s, int dep) -> void {
if(s > K) return;
if(mp.count(K - s)) ans = min(ans, mp[K - s] + dep);
collect.emplace_back(s, dep);
for(auto [z, w]: g[x]) {
if(z != p && vis[z] == 0) {
dfs(dfs, z, x, s + w, dep + 1);
}
}
};
for(auto [z, w]: g[c]) {
if(vis[z] == 0) {
collect.clear();
dfs(dfs, z, c, w, 1);
for(auto [s, dep]: collect) {
if(!mp.count(s) || mp[s] > dep) {
mp[s] = dep;
}
}
}
}
vis[c] = 1;
for(auto [z, w]: g[c]) {
if(vis[z] == 0) {
ans = min(ans, get(z));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
::K = K;
g.resize(N);
sz.resize(N);
vis.resize(N);
for(int i = 0; i < N - 1; ++i) {
int x = H[i][0], y = H[i][1], w = L[i];
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
}
int ans = get(0);
if(ans == INF) return -1;
return ans;
}
