#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
vector<pair<int,int>> e[maxn];
int sz[maxn], heavy[maxn], par[maxn], heavy_par[maxn];
map<int,int> mp;
int ans = 1e9;
void dfs1(int node, int parent){
int heavy_child = -1, sz_child = -1;
for(auto i: e[node]){
if(i.first == parent) continue;
par[i.first] = node;
dfs1(i.first,node);
if(sz[i.first] > sz_child){
heavy_child = i.first;
sz_child = sz[i.first];
}
sz[node]+=sz[i.first];
}
sz[node]+=1;
heavy[node] = heavy_child;
heavy_par[heavy_child] = node;
}
void dfs3(int node, int parent, int dist_now, int depth, vector<array<int,2>> &node_dist, int K){
node_dist.push_back({dist_now, depth});
if(dist_now > K) return;
for(auto i: e[node]){
if(i.first == parent) continue;
dfs3(i.first, node, dist_now+i.second, depth+1, node_dist, K);
}
}
array<int,2> dfs2(int node, int parent, int K){
//go down the heavy child first
// cout<<node<<" "<<parent<<endl;
if(heavy[node] == -1) return {0,0};
// cout<<node<<" "<<parent<<endl;
//first return = total weight added, second return = total edges added
array<int,2> tmp = dfs2(heavy[node],node,K);
int add_weight = tmp[0], add_edge = tmp[1];
add_edge++;
for(auto i: e[node]){
if(i.first == heavy[node]){
add_weight+=i.second;
break;
}
}
mp[-add_weight] = -add_edge;
// for(auto j: mp) cout<<j.first<<" ";
// cout<<endl;
// cout<<"node: "<<node<<" add_weight: "<<add_weight<<" add_edge: "<<add_edge<<endl;
// if(node == 2){
// cout<<"add_weight: "<<add_weight<<endl;
// cout<<mp.begin()->first<<endl;
// }
if(mp.count(K-add_weight) != 0){
ans = min(ans,mp[K-add_weight]+add_edge);
// cout<<"node: "<<node<<endl;
}
//what is the total sum you're adding
vector<array<int,2>> node_dist;
for(auto i: e[node]){
if(i.first!=parent && i.first!=heavy[node]){
dfs3(i.first, node, i.second, 1, node_dist, K); //now I have all the distances
// for(auto j: node_dist) cout<<j[0]<<" "<<j[1]<<endl;
for(auto j: node_dist){
//j[0] = distance, j[1] = minimum edges to cover
if(mp.count(K-add_weight-j[0]) != 0){
// cout<<"node: "<<node<<endl;
ans = min(ans,mp[K-add_weight-j[0]]+j[1]+add_edge);
}
}
//add everything in
for(auto j: node_dist){
if(mp.count(j[0]-add_weight) != 0){
mp[j[0]-add_weight] = min(mp[j[0]-add_weight], j[1]-add_edge);
}
else mp[j[0]-add_weight] = j[1]-add_edge;
}
node_dist.clear();
}
}
return {add_weight, add_edge};
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i = 0;i<N;i++){
par[i] = -1;
heavy_par[i] = -1;
}
for(int i = 0;i<N-1;i++){
e[H[i][0]].push_back(make_pair(H[i][1],L[i]));
e[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
dfs1(0,0); //all the heavy children
// for(int i = 0;i<N;i++){
// cout<<heavy[i]<<" "<<sz[i]<<endl;
// }
// cout<<endl;
for(int i = 0;i<N;i++){
if(heavy_par[i] == -1){
//it's top of a chain
mp[0] = 0;
dfs2(i,par[i],K);
mp.clear();
}
}
if(ans == 1e9) return -1;
else return ans;
}
