#include "race.h" #include <bits/stdc++.h> using namespace std; int best_path(int n_, int k_, int H[][2], int L[]){ int n, k; n = n_; k = k_; vector<vector<pair<int, int>>> adj(n); vector<int64_t> d(n); for(int i = 0; i < n - 1; i++){ int u, v, w; u = H[i][0], v = H[i][1]; w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } vector<vector<int>> jmp(20, vector(n, -1)); vector<int> dep(n), dis(n); auto dfs = [&](int u, int p, auto&& self) -> void{ jmp[0][u] = p; for(int i = 1; i < 20; i++){ if(jmp[i - 1][u] + 1) { jmp[i][u] = jmp[i - 1][jmp[i - 1][u]]; } } for(auto [x, w] : adj[u]){ if(x == p) continue; dep[x] = dep[u] + 1; dis[x] = dis[u] + w; self(x, u, self); } }; dfs(0, -1, dfs); auto lca = [&](int u, int v){ if(dep[u] < dep[v]) swap(u, v); // make u deeper int d = dep[u] - dep[v]; for(int i = 0; i < 20; i++){ if(d >> i & 1) u = jmp[i][u]; } if(u == v) return u; for(int i = 19; i >= 0; i--){ if(jmp[i][u] != jmp[i][v]) u = jmp[i][u], v = jmp[i][v]; } return jmp[0][u]; }; auto get = [&](int u, int v){ return dis[u] + dis[v] - 2 * dis[lca(u, v)]; }; auto get1 = [&](int u, int v){ return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }; vector<int> dn(n), sz(n); auto get_sz = [&](auto&& get_sz, int u, int p) -> void{ sz[u] = 0; for(auto [x, w] : adj[u]){ if(x == p or dn[x]) continue; get_sz(get_sz, x, u); sz[u] += sz[x]; } sz[u]++; }; auto getc = [&](auto&& getc, int u, int p, int nds) -> int{ for(auto [x, w] : adj[u]){ if(x == p or dn[x]) continue; if(sz[x] * 2 > nds){ return getc(getc, x, u, nds); } } return u; }; vector<vector<int>> ntr(n); int root = -1; auto cd = [&](auto&& cd, int ctd, int pr) -> void{ get_sz(get_sz, ctd, -1); int nds = sz[ctd]; ctd = getc(getc, ctd, -1, nds); if(pr != -1) ntr[pr].push_back(ctd); dn[ctd] = 1; if(pr == -1) root = ctd; for(auto [x, w] : adj[ctd]){ if(dn[x]) continue; cd(cd, x, ctd); } }; cd(cd, 0, -1); vector<vector<int>> all(n); vector<map<int64_t, int>> mp(n); int ans = 1e9; auto solve = [&](auto&& solve, int u, int p) -> void{ mp[u][0] = 0; for(auto x : ntr[u]){ if(x == p) continue; solve(solve, x, u); for(auto z : all[x]){ int dist = get(z, u); if(mp[u].count(k - dist)){ ans = min(ans, mp[u][k - dist] + get1(u, z)); } } for(auto z : all[x]){ int dist = get(z, u); int cost = get1(z, u); if(!mp[u].count(dist)) mp[u][dist] = cost; mp[u][dist] = min(mp[u][dist], cost); } all[x].clear(); } all[u].push_back(u); }; solve(solve, root, -1); return (ans > n ? -1 : ans); }