#include "race.h"
#include <iostream>
#include <vector>
#include <utility>
#include <map>
using namespace std;
using ll = long long;
const int MAX_NODES_NUM = 2e5;
const int INF = 1e9 + 7;
int nodes_num, k;
vector<pair<int, int>> tree[MAX_NODES_NUM+7];
bool used[MAX_NODES_NUM];
int sub_tree_size[MAX_NODES_NUM+7];
int res = INF;
void genSubTreeSize(int node, int parent){
sub_tree_size[node] = 1;
for (auto [next_node, _] : tree[node]) if (next_node != parent && !used[next_node]) {
genSubTreeSize(next_node, node);
sub_tree_size[node] += sub_tree_size[next_node];
}
}
int findCentroid(int node, int parent, int N){
for (auto [next_node, _] : tree[node]) if (next_node != parent && !used[next_node])
if (sub_tree_size[next_node] > N/2) return findCentroid(next_node, node, N);
return node;
}
void genPaths(int node, int parent, ll whole_dist, int edges_num, vector<pair<ll, int>>& paths){
if (whole_dist > k) return;
paths.push_back({whole_dist, edges_num});
for (auto [next_node, dist] : tree[node]) if (next_node != parent && !used[next_node])
genPaths(next_node, node, whole_dist + dist, edges_num+1, paths);
}
void processCentroid(int centroid)
{
map<ll, int> prev_paths;
prev_paths[0] = 0;
for (auto [next_node, dist] : tree[centroid]) if (!used[next_node])
{
vector<pair<ll, int>> paths;
genPaths(next_node, centroid, dist, 1, paths);
for (auto [curr_dist, curr_edges_num] : paths){
int x_dist = k-curr_dist;
if (prev_paths.count(x_dist)) res = min(res, prev_paths[x_dist] + curr_edges_num);
}
for (auto [curr_dist, curr_edges_num] : paths)
if (prev_paths.count(curr_dist)) prev_paths[curr_dist] = min(prev_paths[curr_dist], curr_edges_num);
else prev_paths[curr_dist] = curr_edges_num;
}
}
void centroidDecomposition(int node)
{
genSubTreeSize(node, -1);
int centroid = findCentroid(node, -1, sub_tree_size[node]);
processCentroid(centroid);
used[centroid] = true;
for (auto[next_node, _] : tree[centroid])
if (!used[next_node]) centroidDecomposition(next_node);
}
int best_path(int N, int K, int H[][2], int L[])
{
nodes_num = N; k = K;
for (int i = 0; i < nodes_num-1; ++i){
int node_a = H[i][0], node_b = H[i][1], dist = L[i];
tree[node_a].push_back({node_b, dist});
tree[node_b].push_back({node_a, dist});
}
centroidDecomposition(0);
return (res == INF) ? -1 : res;
}
