#include <bits/stdc++.h> using namespace std; int best_path (int n, int k, int h[][2], int l[]) { vector<vector<pair<int, int>>> a(n); for (int i = 0; i < n - 1; i++) { a[h[i][0]].emplace_back(h[i][1], l[i]); a[h[i][1]].emplace_back(h[i][0], l[i]); } long long ans = LONG_LONG_MAX; vector<map<long long, int>> mn(n); vector<long long> dist(n), sum(n); auto dfs = [&] (auto &dfs, int v, int p) -> void{ mn[v][sum[v]] = dist[v]; for (auto [u, w] : a[v]) { if (u != p) { sum[u] = sum[v] + w; dist[u] = dist[v] + 1; dfs(dfs, u, v); } } int g = k + 2 * sum[v]; for (auto [u, w] : a[v]) { if (u != p) { dfs(dfs, u, v); if (mn[v].size() < mn[u].size()) { swap(mn[v], mn[u]); } for (auto [x, y] : mn[u]) { if (mn[v].count(g - x)) { ans = min(ans, y + mn[v][g - x] - 2 * dist[v]); } } for (auto [x, y] : mn[u]) { if (mn[v].count(x)) { mn[v][x] = min(mn[v][x], y); } else mn[v][x] = y; } } } }; dfs(dfs, 0, -1); return (ans == INT_MAX ? -1 : ans); }