#include <bits/stdc++.h>
#define pb push_back
#include "race.h"
#define endl "\n"
#define fastio cin.tie(0); ios_base::sync_with_stdio(false);
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
vector<pair<int, int> > adj[MAXN];
vector<int> sub(MAXN), vis(MAXN);
inline void subtreecalc(int node, int par){
sub[node] = 1;
for(auto itr: adj[node]){
if(itr.first != par && !vis[itr.first]){
subtreecalc(itr.first, node);
sub[node] += sub[itr.first];
}
}
}
inline int find_centroid(int node, int par, int sz){
for(auto itr: adj[node]){
if(vis[itr.first] || itr.first == par) continue;
if(sub[itr.first] > sz/2) return find_centroid(itr.first, node, sz);
}
return node;
}
inline void dfs(int node, int par, int depth, int len, map<int, int> &mpp){
if(vis[node]) return;
if(!mpp[depth]) mpp[depth] = len;
else mpp[depth] = min(mpp[depth], len);
for(auto itr: adj[node]){
if(vis[itr.first] || itr.first == par) continue;
dfs(itr.first, node, depth + itr.second, len + 1, mpp);
}
}
bool compare(pair<int, int> p1, pair<int, int> p2){
return (sub[p1.first] > sub[p2.first]);
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i = 0; i < N-1; i++){
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
int ans = 1e9;
vector<int> roots, new_roots;
roots.pb(0);
int cnt = 0;
while(cnt < N){
for(auto i: roots) subtreecalc(i, i);
for(auto i: roots){
int ct = find_centroid(i, i, sub[i]);
sort(adj[ct].begin(), adj[ct].end(), compare);
int ind = 0;
map<int, int> pre, now;
while(ind < adj[ct].size()){
if(vis[adj[ct][ind].first]){
ind++;
continue;
}
dfs(adj[ct][ind].first, ct, adj[ct][ind].second, 1, now);
for(auto itr: now){
if(pre[K - itr.first]) ans = min(ans, pre[K - itr.first] + now[itr.first]);
if(itr.first == K) ans = min(ans, itr.second);
}
for(auto itr: now){
if(!pre[itr.first] && itr.first != 0) pre[itr.first] = itr.second;
else pre[itr.first] = min(pre[itr.first], now[itr.first]);
}
now.clear();
ind++;
}
vis[ct] = 1;
for(auto itr: adj[ct]){
if(!vis[itr.first]) new_roots.pb(itr.first);
}
cnt++;
}
roots = new_roots;
new_roots.clear();
}
if(ans == 1e9) return -1;
else return ans;
}
