#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); 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<int> dn(n), sz(n); vector<vector<int>> dd(n), ddis(n); auto get_sz = [&](auto&& get_sz, int u, int p, int dep, int64_t dis, int f) -> void{ sz[u] = 0; if(f){ dd[u].push_back(dep); ddis[u].push_back(dis); } for(auto [x, w] : adj[u]){ if(x == p or dn[x]) continue; get_sz(get_sz, x, u, dep + 1, dis + w, f); 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, 0, 0, 0); int nds = sz[ctd]; ctd = getc(getc, ctd, -1, nds); get_sz(get_sz, ctd, -1, 0, 0, 1); 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; // for(auto x : dd){ // cout << x.size() << '\n'; // } // exit(0); auto solve = [&](auto&& solve, int u, int p) -> void{ mp[u][0] = 0; // cerr << u << " " << p << '\n'; for(auto x : ntr[u]){ if(x == p) continue; solve(solve, x, u); for(auto z : all[x]){ // cerr << ddis[z].size() int dist = ddis[z].back(); int cost = dd[z].back(); if(mp[u].count(k - dist)){ ans = min(ans, mp[u][k - dist] + cost); } } for(auto z : all[x]){ int dist = ddis[z].back(); int cost = dd[z].back(); ddis[z].pop_back(); dd[z].pop_back(); if(!mp[u].count(dist)) mp[u][dist] = cost; mp[u][dist] = min(mp[u][dist], cost); all[u].push_back(z); } all[x].clear(); } dd[u].pop_back(); ddis[u].pop_back(); all[u].push_back(u); }; solve(solve, root, -1); return ans > n ? -1 : ans; }