#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; // {weight, edges}
const int INF = 1e7;
vector<vector<pair<int,int>>> g;
vector<int> sz;
vector<bool> vis;
int ans;
void dfs_sz(int u, int p){
sz[u] = 1;
for(auto [v,w]: g[u]){
if(v==p || vis[v]) continue;
dfs_sz(v,u);
sz[u] += sz[v];
}
}
int get_centroid(int u, int tot, int p){
for(auto [v,w]: g[u]){
if(v==p || vis[v]) continue;
if(sz[v]*2 > tot) return get_centroid(v, tot, u);
}
return u;
}
// collect all (weight, edges) from u
void collect(int u, int p, int d, int w, vector<pii> &nodes){
nodes.push_back({w,d});
for(auto [v,wt]: g[u]){
if(v==p || vis[v]) continue;
collect(v,u,d+1,w+wt,nodes);
}
}
// merge two vectors of {weight,edges}, keeping minimal edges per weight
// used to maintain sparse min_edges
void merge(vector<pii> &big, const vector<pii> &small, int K){
vector<pii> temp;
temp.reserve(big.size() + small.size());
for(auto x: big) temp.push_back(x);
for(auto x: small) temp.push_back(x);
sort(temp.begin(), temp.end());
vector<pii> res;
int best = INF;
for(auto [w,e]: temp){
if(w > K) continue;
if(e < best){
best = e;
res.push_back({w,best});
}
}
big = move(res);
}
void solve(int u, int K){
dfs_sz(u,-1);
int c = get_centroid(u, sz[u], -1);
vis[c] = true;
vector<pii> merged; // sparse min_edges, initially empty
merged.push_back({0,0}); // distance 0 with 0 edges
for(auto [v,w]: g[c]){
if(vis[v]) continue;
vector<pii> subtree;
collect(v,c,1,w,subtree);
// query all pairs from subtree and merged to see if total weight == K
for(auto [sw,se]: subtree){
int rem = K - sw;
// binary search merged
auto it = upper_bound(merged.begin(), merged.end(), make_pair(rem,INF));
if(it != merged.begin()){
--it;
int total_edges = se + it->second;
ans = min(ans,total_edges);
}
}
// merge subtree into merged
merge(merged,subtree,K);
}
for(auto [v,w]: g[c]){
if(!vis[v]) solve(v,K);
}
}
int best_path(int N,int K,int H[][2], int L[]){
g.assign(N,{});
sz.assign(N,0);
vis.assign(N,false);
ans = INF;
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]});
}
solve(0,K);
if(ans>=INF) return -1;
return ans;
}
