#include "race.h" #include <algorithm> #include <cassert> #include <functional> #include <utility> #include <vector> // #include <algo.hpp> /* Telebe of Adicto && Mamedov yani AzeTurk810 I see humans but no humanity */ // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using namespace std; #define ln '\n' #define INFi 1e9 #define INFll 1e18 #ifdef ONPC #include <algo.hpp> #else #define dbg(...) #define dbg_out(...) #endif int best_path(int N, int K, int H[][2], int L[]) { // return 0; vector<vector<pair<int, int>>> g(N); for (int i = 0; i < N - 1; i++) { const int &u = H[i][0], &v = H[i][1], &w = L[i]; g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w)); } vector<int> dist(N, 0), lvl(N), par(N); int res = -1; function<void(int, int)> dfs = [&](int v, int pa) { par[v] = pa; dbg(v); dbg(pa); // dbg(pa); // dbg(lvl); for (auto [u, w] : g[v]) { if (u == pa) continue; dist[u] = dist[v] + w; lvl[u] = lvl[v] + 1; dfs(u, v); } if (dist[v] == K) { if (res == -1 || lvl[res] > lvl[v]) { res = v; } } }; int ans = INFi; for (int i = 0; i < N; i++) { dist[i] = 0; lvl[i] = 0; res = -1; par[i] = -1; dfs(i, -1); if (res != -1) ans = min(ans, lvl[res]); dbg(i); dbg(lvl); } if (ans == INFi) ans = -1; return ans; } // Attack on titan<3 // Just Imaginary /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */