#include "race.h" #include <bits/stdc++.h> // solved by bekagg #define ll long long #define ent '\n' #define pb push_back #define all(x) x.begin(),x.end() #define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; const int N = 5e5+5; const int MOD = 1e9+7; ll d[N] , ans = INT_MAX; ll dist; ll t[N]; vector< pair<ll , ll> >g[N]; map<ll , ll> mp[N]; void dfs(ll v , ll p){ mp[v][t[v]] = d[v]; for (auto [to , c] : g[v]){ if (to == p) continue; d[to] = d[v] + 1; t[to] = t[v] + c; dfs(to , v); if (mp[v].size() < mp[to].size()){ swap(mp[to] , mp[v]); } for (auto [too , c] : mp[to]){ if (c == 0 or mp[v][(dist - too + 2 * t[v])] == 0) continue; ans = min(ans , mp[v][(dist - too + 2 * t[v])] + c - 2 * d[v]); } for (auto [too , c] : mp[to]){ if (c == 0) continue; if (mp[v][too] == 0) mp[v][too] = c; else mp[v][too] = min(mp[v][too] , c); } } // to2 - d[v] = k - (to1 - d[v]) // to2 - d[v] = k - to1 + d[v] // to2 = k - to1 + 2 * d[v] } int best_path(int n , int k , int h[][2] , int l[]){ dist = k; for (ll i = 0; i < n - 1; i++){ h[i][0]++; h[i][1]++; g[h[i][0]].pb({h[i][1] , l[i]}); g[h[i][1]].pb({h[i][0] , l[i]}); } d[1] = 1; dfs(1 , 0); return (ans == INT_MAX ? -1 : ans); }