#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 2e5 + 5;
vector<pii> g[MAX];
ll dist[MAX];
ll height[MAX];
int k = 0;
void dfs1(int node, int p, int h, ll d){
dist[node] = d;
height[node] = h;
for(pii to:g[node]){
if(to.first == p) continue;
dfs1(to.first, node, h + 1, d + to.second);
}
}
int search(set<pair<ll, int>>& s, ll d){
auto itr = s.lower_bound({d, 0});
if(itr != s.end()){
if((itr->first) == d){
return itr->second;
}
else{
return -1;
}
}
else{
return -1;
}
}
ll ans = MAX;
set<pair<ll, int>> sets[MAX];
void dfs2(int node, int p){
for(pii to:g[node]){
if(to.first == p) continue;
dfs2(to.first, node);
int h = search(sets[to.first], dist[node] + k);
if(h != -1) ans = min(ans, h - height[node]);
if(sets[to.first].size() > sets[node].size()){
swap(sets[to.first], sets[node]);
}
}
for(pii to:g[node]){
if(to.first == p) continue;
for(auto& p:sets[to.first]){
int h = search(sets[node], k - p.first + (dist[node] << 1));
if(h != -1) ans = min(ans, h + p.second - (height[node] << 1));
}
for(auto& p:sets[to.first]){
sets[node].insert(p);
}
}
sets[node].insert({dist[node], height[node]});
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
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]});
}
dfs1(0, 0, 0, 0);
dfs2(0, 0);
if(ans == MAX) return -1;
else return ans;
}
