#include "race.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int mod = 1e9 + 7, N = 2e5 + 5;
int n, k, ans = INT_MAX;
vector<int> adj[N], subtree_size(N);
vector<bool> is_removed(N);
vector<pair<int, int>> cur;
map<pair<int, int>, int> l;
void dfs(int v, int par, int dist, int edge){
if(dist > k || edge > ans) return;
cur.push_back({dist, edge});
for(auto to : adj[v]){
if(to == par || is_removed[to]) continue;
dfs(to, v, dist + l[{v, to}], edge + 1);
}
}
int get_subtree_size(int node, int parent = -1) {
subtree_size[node] = 1;
for (int child : adj[node]) {
if (child == parent || is_removed[child]) { continue; }
subtree_size[node] += get_subtree_size(child, node);
}
return subtree_size[node];
}
int get_centroid(int node, int tree_size, int parent = -1) {
for (int child : adj[node]) {
if (child == parent || is_removed[child]) { continue; }
if (subtree_size[child] * 2 > tree_size) {
return get_centroid(child, tree_size, node);
}
}
return node;
}
void build_centroid_decomp(int node = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
map<int, int> mp;
for(int x : adj[centroid]){
if(is_removed[x]) continue;
dfs(x, centroid, l[{centroid, x}], 1);
for(auto pr : cur){
if(pr.first == k) ans = min(ans, pr.second);
else if(mp.find(k - pr.first) != mp.end()){
ans = min(ans, mp[k - pr.first] + pr.second);
}
}
for(auto pr : cur){
if(mp.find(pr.first) == mp.end()){
mp[pr.first] = pr.second;
}else mp[pr.first] = min(mp[pr.first], pr.second);
}
cur.clear();
}
is_removed[centroid] = true;
for (int child : adj[centroid]) {
if (is_removed[child]) { continue; }
build_centroid_decomp(child);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0; i < n - 1; i++){
int x = H[i][0], y = H[i][1];
adj[x].push_back(y);
adj[y].push_back(x);
l[{x, y}] = l[{y, x}] = L[i];
}
build_centroid_decomp();
return (ans == INT_MAX ? -1 : ans);
}
//main(){
// ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
// int tt = 1; //cin >> tt;
// while(tt--){
// int N, K;
// cin >> N >> K;
// int H[N][2], L[N];
// for(int i = 0; i < N - 1; i++){
// cin >> H[i][0] >> H[i][1];
// }
// for(int i = 0; i < N - 1; i++){
// cin >> L[i];
// }
// cout << best_path(N, K, H, L) << endl;
// }
//}
