#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 69;
int n, k;
vector <pair<int, int>> adj[maxn];
bool del[maxn];
int sz[maxn];
map <int, int> mp;
vector <int> comp;
int ans = 1e9;
vector <pair<int, int>> vec;
void dfs(int u, int par, int dist, int dep = 1){
if (dist > k) return;
vec.push_back(make_pair(dist, dep));
if (mp.find(k - dist) != mp.end()){
ans = min(ans, mp[k - dist] + dep);
}
for (auto [v, w] : adj[u]){
if (!del[v] && v != par){
dfs(v, u, dist + w, dep + 1);
}
}
}
void dfs2(int u, int par){
sz[u] = 1;
comp.push_back(u);
for (auto [v, w] : adj[u]){
if (!del[v] && v != par){
dfs2(v, u);
sz[u] += sz[v];
}
}
}
int find(int x){
comp.clear();
dfs2(x, -1);
for (auto u : comp){
int mx = 0;
for (auto [v, w] : adj[u]){
if (!del[v] && sz[v] < sz[u])
mx = max(mx, sz[v]);
}
mx = max(mx, (int)comp.size() - 1 - sz[u]);
// cout << u << " " << mx << "\n";
if (2 * mx <= (int)comp.size()) return u;
}
// for (auto x : comp){
// cout << x << " " << sz[x] << "\n";
// }
// exit(0);
assert(false);
}
void cd(int x){
x = find(x);
mp.clear();
mp[0] = 0;
int u = x;
for (auto [v, w] : adj[u]){
if (!del[v]){
dfs(v, u, w);
for (auto [x, y] : vec){
if (mp.find(x) == mp.end()) mp[x] = y;
else mp[x] = min(mp[x], y);
}
vec.clear();
}
}
del[x] = true;
for (auto [v, w] : adj[x]){
if (!del[v]){
cd(v);
}
}
}
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 u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
cd(0);
if (ans == 1e9) return -1;
else return ans;
}
// int main(){
// int n, k; cin >> n >> k;
// int H[n - 1][2], L[n - 1];
// 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);
// return 0;
// }
