#include "race.h" #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define all(a) a.begin(), a.end() #define ff(i,a,b) for(int i=a;i<=b;i++) #define fb(i,b,a) for(int i=b;i>=a;i--) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 200005; const int inf = 1e9 + 5; int n, k; vector<pii> g[maxn]; int rez = inf; int h[maxn]; int d[maxn]; int cnt[maxn]; bool bio[maxn]; void dfs_size(int v, int p){ cnt[v] = 1; for(auto c : g[v]){ int u = c.fi; // int w = c.se; if(u == p || bio[u])continue; dfs_size(u, v); cnt[v] += cnt[u]; } } int centroid(int v, int p, int vel){ for(auto c : g[v]){ int u = c.fi; // int w = c.se; if(u == p || bio[u])continue; if(cnt[u] > vel / 2)return centroid(u, v, vel); } return v; } map<int,int> kol; vector<pii> cuvaj; void dfs_resi(int v, int p){ cuvaj.pb({d[v], h[v]}); if(kol.count(k - d[v]))rez = min(rez, kol[k - d[v]] + h[v]); for(auto c : g[v]){ int u = c.fi; int w = c.se; if(u == p || bio[u])continue; h[u] = h[v] + 1; d[u] = d[v] + w; dfs_resi(u, v); } } void decompose(int v, int p){ dfs_size(v, p); int cen = centroid(v, p, cnt[v]); // cout << endl; // cout << "cen: " << cen << endl; bio[cen] = 1; d[cen] = 0; h[cen] = 0; kol.clear(); kol[0] = 0; for(auto c : g[cen]){ int u = c.fi; int w = c.se; if(u == p || bio[u])continue; cuvaj.clear(); d[u] = w; h[u] = 1; dfs_resi(u, cen); for(auto c : cuvaj){ // cout << c.fi << " " << c.se << endl; if(!kol.count(c.fi))kol[c.fi] = c.se; else kol[c.fi] = min(kol[c.fi], c.se); } // cout << endl; } for(auto c : g[cen]){ int u = c.fi; // int w = c.se; if(u == p || bio[u])continue; decompose(u, cen); } } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; ff(i,0,n - 1){ g[H[i][0]].pb({H[i][1], L[i]}); g[H[i][1]].pb({H[i][0], L[i]}); } rez = inf; decompose(1, -1); return (rez > n ? -1 : rez); } //int main() //{ // ios::sync_with_stdio(false); // cout.tie(nullptr); // cin.tie(nullptr); // cin >> n >> k; // ff(i,1,n - 1){ // int u, v, w; // cin >> u >> v >> w; // g[u].pb({v, w}); // g[v].pb({u, w}); // } // decompose(1, -1); // cout << (rez == inf ? -1 : rez) << endl; // return 0; //} /** 4 3 1 2 1 2 3 2 2 4 4 3 3 1 2 1 2 3 1 11 12 1 2 3 1 3 4 3 4 5 4 5 4 5 6 6 1 7 3 7 8 2 7 9 5 9 10 6 9 11 7 6 7 1 2 1 1 3 1 2 5 3 2 4 8 5 6 2 **/