#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int K = 1e6+10;
vector<vector<pair<int,int>>> g;
vector<int> min_edges(K,1e7);
vector<int> vis;
vector<int> sz;
vector<int> dist;
vector<int> wt;
int ans = 1e7;
void dfs(int u, int p = -1){
sz[u] = 1;
for(auto [v,w]: g[u]){
if(v == p || vis[v]) continue;
dfs(v,u);
sz[u] += sz[v];
}
return;
}
int get_centroid(int tot, int u, int p = -1){
for(auto [v,w]: g[u]){
if(v == p || vis[v]) continue;
if(2*sz[v] > tot) return get_centroid(tot,v,u);
}
return u;
}
void get_dis(vector<int> &nodes, vector<int> &dist, vector<int> &wt, int k, int u, int p = -1){
nodes.push_back(u);
for(auto [v,w]: g[u]){
if(v == p || vis[v]) continue;
dist[v] = 1 + dist[u];
wt[v] = w+wt[u];
get_dis(nodes,dist,wt,k,v,u);
}
}
void calculate_min(int n, int k, int u, int p = -1){
dfs(u,p);
int r = get_centroid(sz[u], u, p);
// cout << "centroid: " << r << "\n";
vis[r] = 1;
min_edges[0] = 0;
for(auto[v,w]: g[r]){
if(vis[v] || v == p) continue;
vector<int> nodes;
dist[v] = 1;
wt[v] = w;
get_dis(nodes,dist,wt,k,v,r);
for(int v: nodes){
if(wt[v] <= k) ans = min(ans, min_edges[k-wt[v]]+dist[v]);
}
for(int v: nodes){
if(wt[v] <= k) min_edges[wt[v]] = min(min_edges[wt[v]],dist[v]);
}
}
min_edges.assign(k+1,1e7);
for(auto [v,w]: g[r]){
if(vis[v] || v == p) continue;
calculate_min(n,k,v,r);
}
}
int best_path(int n, int k, int h[][2], int l[]){
g.resize(n+1);
vis.assign(n+1,0);
sz.resize(n+1);
dist.assign(n+1,1e7);
wt.assign(n+1,1e7);
for(int i=0; i<n-1; i++){
g[h[i][0]].push_back({h[i][1],l[i]});
g[h[i][1]].push_back({h[i][0],l[i]});
}
calculate_min(n,k,0);
if(ans >= 1e7) return -1;
return ans;
}
// int32_t main(){
// int n,k; cin >> n >> k;
// int h[n-1][2];
// for(int i=0; i<n-1; i++) cin >> h[i][0] >> h[i][1];
// int l[n-1];
// for(int i=0; i<n-1; i++) cin >> l[i];
// int r = best_path(n,k,h,l);
// cout << r << "\n";
// // for(int i=0; i<=k; i++) cout << min_edges[i] << " ";
// // cout << "\n";
// return 0;
// }
