#include "race.h"
#include <iostream>
#include <vector>
using namespace std;
const int inf = 1e9;
const int N = 200005;
const int K = 1000001;
vector<pair<int, int>> g[N];
int sub[N], f[K], k;
bool del[N];
int ans = inf;
void calcsub(int node, int par){
sub[node] = 1;
for(auto t : g[node]){
int v = t.first;
if(v == par || del[v])continue;
calcsub(v, node);
sub[node] += sub[v];
}
}
int centroid(int node, int par, int T){
int mx = -1;
for(auto t : g[node]){
int v = t.first;
if(v == par || del[v])continue;
if(mx == -1 || sub[mx] < sub[v]){
mx = v;
}
}
if(mx != -1 && sub[mx] > T / 2)return centroid(mx, node, T);
return node;
}
void calc(int node, int par, int d, int h){
if(k >= d)ans = min(ans, f[k - d] + h);
for(auto t : g[node]){
int v = t.first, w = t.second;
if(v == par || del[v])continue;
calc(v, node, d + w, h + 1);
}
}
void upd(int node, int par, int d, int h){
if(d <= k)f[d] = min(f[d], h);
for(auto t : g[node]){
int v = t.first, w = t.second;
if(v == par || del[v])continue;
upd(v, node, d + w, h + 1);
}
}
void clear(int node, int par, int d){
if(d <= k)f[d] = inf;
for(auto t : g[node]){
int v = t.first, w = t.second;
if(v == par || del[v])continue;
clear(v, node, d + w);
}
}
void decompose(int node){
calcsub(node, node);
int C = centroid(node, node, sub[node]);
del[C] = 1;
f[0] = 0;
for(auto t : g[C]){
int v = t.first, w = t.second;
if(del[v])continue;
calc(v, v, w, 1);
upd(v, v, w, 1);
}
f[0] = inf;
for(auto t : g[C]){
int v = t.first, w = t.second;
if(del[v])continue;
clear(v, v, w);
}
for(auto t : g[C]){
int v = t.first;
if(del[v])continue;
decompose(v);
}
}
int best_path(int n, int _K, int h[][2], int l[]){
k = _K;
for(int i = 0;i <= _K;++i){
f[i] = inf;
}
for(int i = 0;i < n - 1;++i){
int u = h[i][0], v = h[i][1], w = l[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(0);
if(ans == inf)ans = -1;
return ans;
}
// int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int n, k;
// cin >> n >> k;
// int h[n - 1][2], l[n - 1];
// for(int i = 0;i < n - 1;++i){
// int u, v;
// cin >> u >> v;
// h[i][0] = u;
// h[i][1] = v;
// }
// for(int i = 0;i < n - 1;++i){
// int w;
// cin >> w;
// l[i] = w;
// }
// cout << best_path(n, k, h, l) << '\n';
// }
