#include "race.h"
#include <vector>
#include <map>
struct Graph {
private:
std::vector<std::vector<std::pair<int, int>>> adj;
int size;
std::vector<int> subtree;
std::vector<bool> removed;
std::map<int, int> min_edges;
int answer = -1;
int calc_subtree(int node, int root = -1) {
subtree[node] = 1;
for (const auto &[x, weight]: adj[node]) {
if (x == root || removed[x]) continue;
subtree[node] += calc_subtree(x, node);
}
return subtree[node];
}
int find_centroid(int node, int tree_size, int root = -1) {
for (const auto &[x, weight]: adj[node]) {
if (x == root || removed[x]) continue;
if (subtree[x] > tree_size / 2) return find_centroid(x, tree_size, node);
}
return node;
}
void search(int node, int root, bool assign, int sum, int target, int depth) {
if (sum > target) return;
if (assign) {
if (min_edges[sum] == 0 || depth < min_edges[sum]) min_edges[sum] = depth;
} else {
if (sum == target) {
if (answer == -1 || depth < answer) answer = depth;
} else {
if (min_edges[target - sum] != 0) {
if (answer == -1 || min_edges[target - sum] + depth < answer) {
answer = min_edges[target - sum] + depth;
}
}
}
}
for (const auto &[x, weight]: adj[node]) {
if (x == root || removed[x]) continue;
search(x, node, assign, sum + weight, target, depth + 1);
}
}
void decompose(int node, int target) {
int centroid = find_centroid(node, calc_subtree(node));
removed[centroid] = true;
for (const auto &[x, weight]: adj[centroid]) {
if (removed[x]) continue;
search(x, centroid, false, weight, target, 1);
search(x, centroid, true, weight, target, 1);
}
min_edges.clear();
for (const auto &[x, weight]: adj[centroid]) {
if (removed[x]) continue;
decompose(x, target);
}
}
public:
explicit Graph(int size) : size(size) {
adj.resize(size);
subtree.resize(size, 0);
removed.resize(size, false);
}
void add_edge(int x, int y, int c) {
adj[x].emplace_back(y, c);
adj[y].emplace_back(x, c);
}
int get_answer(int target) {
decompose(0, target);
return answer;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
Graph tree(N);
for (int i = 0; i < N - 1; ++i) {
tree.add_edge(H[i][0], H[i][1], L[i]);
}
return tree.get_answer(K);
}
