#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector <int> VI;
typedef vector < vector <int> > VVI;
typedef vector < vector < pair <int, int> > > VVPII;
typedef vector <ll> VLL;
struct Data {
ll dst;
int lvl;
bool operator <(const Data &other) const {
if(dst == other.dst) {
return lvl < other.lvl;
}
return dst < other.dst;
}
};
void dfs(int nod, int par, VVPII &g, int &ans, vector < multiset <Data> > &mst, VLL &Dst, VI &Lvl, int k) {
for(auto it : g[nod]) {
if(it.first != par) {
Lvl[it.first] = Lvl[nod] + 1, Dst[it.first] = Dst[nod] + it.second;
dfs(it.first, nod, g, ans, mst, Dst, Lvl, k);
if(mst[nod].size() < mst[it.first].size()) {
swap(mst[nod], mst[it.first]);
}
}
}
for(auto it : g[nod]) {
if(it.first != par) {
for(auto cur : mst[it.first]) {
auto itr = mst[nod].lower_bound({k + 2LL * Dst[nod] - cur.dst, 0});
if(itr != mst[nod].end() && itr -> dst + cur.dst - 2LL * Dst[nod] == k) {
ans = min(ans, itr -> lvl + cur.lvl - 2 * Lvl[nod]);
}
}
for(auto cur : mst[it.first]) {
mst[nod].insert(cur);
}
}
}
auto itr = mst[nod].lower_bound({k + Dst[nod], 0});
if(itr != mst[nod].end() && itr -> dst - Dst[nod] == k) {
ans = min(ans, itr -> lvl - Lvl[nod]);
}
mst[nod].insert({Dst[nod], Lvl[nod]});
}
int best_path(int n, int k, int H[][2], int L[]) {
VVPII g(n + 1);
for(int i = 0; i < n - 1; i++) {
H[i][0]++, H[i][1]++;
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
vector < multiset <Data> > mst(n + 1);
VLL dst(n + 1); VI lvl(n + 1);
int ans = 2 * n;
dfs(1, 0, g, ans, mst, dst, lvl, k);
if(ans == 2 * n) {
ans = -1;
}
return ans;
}
