#include "race.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int best_path(int N, int K, int H[][2], int L[])
{
ll n, k;
n=N;
k=K;
vector<vector<pair<ll, ll>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
ll u, v, l;
u=H[i][0];
v=H[i][1];
l=L[i];
adj[u].push_back({v, l});
adj[v].push_back({u, l});
}
vector<ll> dist(n);
vector<ll> depth(n);
function<void(ll, ll)> dfs = [&](ll u, ll p) {
for (auto i: adj[u]) {
if (i.first != p) {
depth[i.first] = depth[u] + 1;
dist[i.first] = dist[u] + i.second;
dfs(i.first, u);
}
}
};
dfs(0, -1);
ll ans = LLONG_MAX;
vector<map<ll, ll>> mp(n);
function<void(ll, ll)> dfs2 = [&](ll u, ll p) {
mp[u][dist[u]] = depth[u];
for (auto &[v, d]: adj[u]) {
if (v != p) {
dfs2(v, u);
if (mp[v].size() > mp[u].size()) {
swap(mp[u], mp[v]);
}
for (auto &[de, mi]: mp[v]) {
if (mp[u].find(dist[u] + k - (de - dist[u])) != mp[u].end()) {
ans = min(ans, mi + mp[u][dist[u] + k - (de - dist[u])] - 2*depth[u]);
}
}
for (auto &[de, mi]: mp[v]) {
if (mp[u].find(de) == mp[u].end()) {
mp[u][de] = mi;
} else {
mp[u][de] = min(mp[u][de], mi);
}
}
}
}
};
dfs2(0, -1);
if (ans == LLONG_MAX) {
return -1;
} else {
return ans;
}
}
