#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> subtree_size;
vector<int> seen;
int total_nodes;
int target_k;
int best_ans = INT_MAX;
int dfs(int node, int par) {
int sz = 1;
for (auto [neiDist, neiNode] : adj[node]) {
if (neiNode == par || seen[neiNode]) continue;
sz += dfs(neiNode, node);
}
return subtree_size[node] = sz;
}
int centroid(int node, int par) {
for (auto [neiDist, neiNode] : adj[node]) {
if (neiNode == par || seen[neiNode]) continue;
if (subtree_size[neiNode] > total_nodes / 2) {
return centroid(neiNode, node);
}
}
return node;
}
void dfs2(int node, int par, int dist, int edges, unordered_map<int, int>& mp) {
if (dist > target_k) return;
if (mp.count(target_k - dist)) {
best_ans = min(best_ans, edges + mp[target_k - dist]);
}
for (auto [neiDist, neiNode] : adj[node]) {
if (neiNode == par || seen[neiNode]) continue;
dfs2(neiNode, node, dist + neiDist, edges + 1, mp);
}
}
void add_to_map(int node, int par, int dist, int edges, unordered_map<int, int>& mp) {
if (dist > target_k) return;
if (!mp.count(dist)) {
mp[dist] = edges;
} else {
mp[dist] = min(mp[dist], edges);
}
for (auto [neiDist, neiNode] : adj[node]) {
if (neiNode == par || seen[neiNode]) continue;
add_to_map(neiNode, node, dist + neiDist, edges + 1, mp);
}
}
void solve(int node) {
dfs(node, -1);
total_nodes = subtree_size[node];
int c = centroid(node, -1);
seen[c] = 1;
unordered_map<int, int> mp;
mp[0] = 0;
for (auto [neiDist, neiNode] : adj[c]) {
if (seen[neiNode]) continue;
unordered_map<int, int> current_mp;
dfs2(neiNode, c, neiDist, 1, mp);
add_to_map(neiNode, c, neiDist, 1, mp);
}
for (auto [neiDist, neiNode] : adj[c]) {
if (seen[neiNode]) continue;
solve(neiNode);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
subtree_size.resize(N);
adj.resize(N);
seen.resize(N, 0);
target_k = K;
for (int i = 0; i < N-1; ++i) {
adj[H[i][0]].push_back({L[i], H[i][1]});
adj[H[i][1]].push_back({L[i], H[i][0]});
}
solve(0);
if (best_ans == INT_MAX) {
return -1;
}
return best_ans;
}
