#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int mn = INT_MAX;
map<int, int> dfs(vector<pair<int, int>> ap[], int cur, int par, int l, int h, int k)
{
map<int, int> mp;
mp[l] = h;
//cout << cur << '\n';
for (auto& [p, len] : ap[cur]) {
if (p == par) continue;
map<int, int> mp2 = dfs(ap, p, cur, l + len, h + 1, k);
if (mp2.size() > mp.size()) swap(mp, mp2);
for (auto& [v, d] : mp2) {
if (mp.find(k + 2 * l - v) != mp.end()) mn = min(d + mp[k + 2 * l - v] - 2 * h, mn);
}
for (auto& [v, d] : mp2) {
if (mp.find(v) != mp.end()) mp[v] = min(mp[v], d);
else mp[v] = d;
}
}
// cout << cur << '\n';
// for (auto& p : mp) cout << p.first << ' ' << p.second << '\n';
// cout << '\n';
return mp;
}
int best_path(int n, int k, int h[][2], int l[]) {
vector<pair<int, int>> ap[n + 1];
for (int i = 0; i < n - 1; i++) {
ap[h[i][0]].push_back({h[i][1], l[i]});
ap[h[i][1]].push_back({h[i][0], l[i]});
}
dfs(ap, 0, -1, 0, 0, k);
return (mn == INT_MAX ? -1 : mn);
}
/**
mp: curlen, min - dep
a + b - 2 * lca(a, b) = k
*/
