#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
const int MAXN = 500010;
vector<pair<int,int>> v[MAXN];
map<ll,multiset<int>> w2e;
int get(ll h){
return *w2e[h].begin();
}
void erase(ll h, int x){
w2e[h].erase(w2e[h].find(x));
if(w2e[h].size() == 0) w2e.erase(h);
}
void add(ll h, int x){
w2e[h].insert(x);
}
int k, ans;
namespace sack{
int T;
int t_in[MAXN], t_out[MAXN], t2node[MAXN];
int sz[MAXN];
int depth[MAXN];
ll wdepth[MAXN];
void precalc(int x, int par=-1, int d=0, ll dw=0){
t2node[T] = x; t_in[x] = T++; sz[x] = 1;
depth[x] = d, wdepth[x] = dw;
for(auto [y, w] : v[x]) if(y != par) {
precalc(y, x, d + 1, dw + w);
sz[x] += sz[y];
}
t_out[x] = T;
}
void solve(int x, int par=-1, bool keep=0){
int hc = -1; // heavy_child
for(auto [y, w] : v[x]) if(y != par) {
if(hc == -1 || sz[y] > sz[hc]) hc = y;
}
if(hc != -1){
// solve but dont keep light nodes
for(auto [y, w] : v[x]) if(y != par && y != hc)
solve(y, x, false);
// solve and keep heavy nodes
solve(hc, x, true);
}
for(auto [y, w] : v[x]) if(y != par && y != hc) {
// maybe solve queries (light -> (heavy + past_lights))
for(int t = t_in[y]; t < t_out[y]; ++t){
int z = t2node[t];
// query z
ll goal = wdepth[x] * 2 + k;
ll missing = goal - wdepth[z];
int my_edges = depth[z] - depth[x];
// cout << "oi " << x << " " << z << "\n";
// cout << goal << " " << missing << "\n";
if(w2e.count(missing)){
int friend_edges = get(missing) - depth[x];
// cout << "in " << friend_edges << " " << my_edges << endl;
ans = min(ans, my_edges + friend_edges);
}
}
// add light nodes after solving, avoid info leakage
for(int t = t_in[y]; t < t_out[y]; ++t){
int z = t2node[t];
// add z
add(wdepth[z], depth[z]);
}
}
// solve queries (x -> all subtrees)
if(w2e.count(wdepth[x] + k)){
ans = min(ans, get(wdepth[x] + k) - depth[x]);
}
// add x for querying or for keeping as heavy child
add(wdepth[x], depth[x]);
if(!keep){
for(int t = t_in[x]; t < t_out[x]; ++t){
int z = t2node[t];
// rmv z
erase(wdepth[z], depth[z]);
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i = 0; i < N; ++i) v[i].clear();
for(int i = 0; i + 1 < N; ++i){
int a = H[i][0], b = H[i][1];
int c = L[i];
v[a].push_back({b, c});
v[b].push_back({a, c});
}
ans = INT_MAX;
k = K;
sack::precalc(0);
sack::solve(0);
if(ans == INT_MAX) return -1;
else return ans;
}
// int32_t main(){
// int n, k; cin >> n >> k;
// int h[n-1][2];
// int l[n-1];
// for(int i = 0; i < n-1; ++i){
// cin >> h[i][0] >> h[i][1] >> l[i];
// }
// cout << best_path(n, k, h, l);
// int x; cin >> x;
// cout << " " << x << "\n";
// }
