#include "race.h" #include <algorithm> #include <cassert> #include <functional> #include <map> #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 struct CentroiddeComposition { int _n_, _k_, _ans_; vector<vector<pair<int, int>>> g; vector<bool> removed; vector<int> subSize, distFromCentroid, nodeFromCentroid; vector<vector<int>> level; map<int, int> mp, mp_same; CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi) { removed.assign(_n + 1, false); distFromCentroid.assign(_n + 1, INFi); nodeFromCentroid.assign(_n + 1, INFi); subSize.resize(_n + 1); level.resize(_n + 1); } int getSubSize(int v, int pa = -1) { subSize[v] = 1; for (const auto &[u, w] : g[v]) { if (u == pa || removed[u]) continue; getSubSize(u, v); subSize[v] += subSize[u]; } return subSize[v]; } void getDistFromCentroid(int v, int pa) { // if (distFromCentroid[v] > _k_) XXX: it can be in the same subtree // return; // INFO: is it in other side of centroid??? if (distFromCentroid[v] <= _k_) { int target = _k_ - distFromCentroid[v]; if (mp.find(target) != mp.end()) { _ans_ = min(_ans_, mp[target] + nodeFromCentroid[v]); } if (mp.find(distFromCentroid[v]) == mp.end()) mp[distFromCentroid[v]] = nodeFromCentroid[v]; if (mp_same.find(distFromCentroid[v]) == mp_same.end()) mp_same[distFromCentroid[v]] = nodeFromCentroid[v]; mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]); mp_same[distFromCentroid[v]] = max(mp_same[distFromCentroid[v]], nodeFromCentroid[v]); } for (const auto &[u, w] : g[v]) { if (pa == u || removed[u]) continue; distFromCentroid[u] = distFromCentroid[v] + w; nodeFromCentroid[u] = nodeFromCentroid[v] + 1; getDistFromCentroid(u, v); } } int findCentroid(int v, int half, int pa = -1) { for (const auto &[u, w] : g[v]) { if (u == pa || removed[u] || subSize[u] <= half) { continue; } return findCentroid(u, half, v); } return v; } int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab // WARNING: You must initilaze before getDistFromCentroid Manualy // nodeFromCentroid[v] = 0; // distFromCentroid[v] = 0; // mp.clear(); // mp_same.clear(); // getDistFromCentroid(v, -1); nodeFromCentroid[centroid] = 0; distFromCentroid[centroid] = 0; mp.clear(); mp_same.clear(); getDistFromCentroid(centroid, -1); return _ans_; } int build(int v = 0, int id = 0) { // TODO: Inside int centroid = findCentroid(v, getSubSize(v) >> 1); removed[centroid] = true; solve(centroid, subSize[v]); for (const auto &[u, w] : g[centroid]) { if (removed[u]) continue; level[id + 1].push_back(build(u, id + 1)); // WARNING: should it be id + 1 or id ??? } return centroid; } }; 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)); } CentroiddeComposition t(N, g, K); t.level[0].push_back(t.build(0)); if (t._ans_ == INFi) t._ans_ = -1; return t._ans_; // WARNING: Asigisi brute force. int res = -1; vector<int> dist(N, 0), lvl(N), par(N); function<void(int, int)> dfs = [&](int v, int pa) { par[v] = pa; 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 /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */