#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 */