#include <bits/stdc++.h>
#include "race.h"
using namespace std;
class Solver{
private:
vector<vector<int>> &adj;
map<pair<int, int>, long long> &weight;
vector<int> subtree_size;
vector<bool> is_removed;
long long goal;
int res;
int get_subtree_size(int curr, int parent = -1){
subtree_size[curr] = 1;
for (int child : adj[curr]){
if (child == parent || is_removed[child]) continue;
subtree_size[curr] += get_subtree_size(child, curr);
}
return subtree_size[curr];
}
int get_centroid(int curr, int tree_size, int parent = -1){
for (int child : adj[curr]){
if (child == parent || is_removed[child]) continue;
if (subtree_size[child] * 2 > tree_size) return get_centroid(child, tree_size, curr);
}
return curr;
}
void build_centroid_decomp(int curr = 0){
int centroid = get_centroid(curr, get_subtree_size(curr));
is_removed[centroid] = true;
map<long long, int> cnt;
cnt[0] = 1;
for (int child : adj[centroid]){
if (!is_removed[child]){
dfs(child, centroid, 1, weight[make_pair(centroid, child)], true, cnt);
dfs(child, centroid, 1, weight[make_pair(centroid, child)], false, cnt);
}
}
for (int child : adj[centroid]) if (!is_removed[child]) build_centroid_decomp(child);
}
void dfs(int curr, int parent, int depth, long long dist, bool type, map<long long, int> &cnt){
if (dist > goal) return;
if (type){
if (cnt.find(goal - dist) != cnt.end()) res = min(res, depth + cnt[goal - dist]);
}
else {
if (cnt.find(dist) == cnt.end()) cnt[dist] = depth;
else cnt[dist] = min(cnt[dist], depth);
}
for (int child : adj[curr]){
if (child == parent || is_removed[child]) continue;
dfs(child, curr, depth + 1, dist + weight[make_pair(curr, child)], type, cnt);
}
}
public:
Solver(vector<vector<int>> &_adj, map<pair<int, int>, long long> &_weight, long long _goal) : adj(_adj), weight(_weight), subtree_size(adj.size()), is_removed(adj.size(), false), goal(_goal), res(INT_MAX) {
build_centroid_decomp();
}
int get_res() {return res;}
};
int best_path(int N, int K, int H[][2], int L[]){
vector<vector<int>> adj(N);
map<pair<int, int>, long long> weight;
for (int i = 0; i < N - 1; i++){
int u = H[i][0], v = H[i][1];
long long w = L[i];
adj[u].push_back(v);
adj[v].push_back(u);
weight[make_pair(u, v)] = w;
weight[make_pair(v, u)] = w;
}
Solver solver(adj, weight, K);
int res = solver.get_res();
return res < INT_MAX ? res : -1;
}
