#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 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; } int kol[5 * maxn]; vector<pii> cuvaj; void dfs_resi(int v, int p, int duz, int pw){ if(pw > k)return; // cout << "v: " << v << endl; // cout << "d[v]: " << duz << endl; // cout << "h[v]: " << pw << endl; cuvaj.pb({pw, duz}); // cout << "rez: " << kol[k - d[v]] + h[v] << endl; rez = min(rez, kol[k - pw] + duz); // cout << endl; for(auto c : g[v]){ int u = c.fi; int w = c.se; if(u == p || bio[u])continue; dfs_resi(u, v, duz + 1, pw + w); } } 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; vector<int> pom; for(auto c : g[cen]){ int u = c.fi; int w = c.se; if(u == p || bio[u])continue; cuvaj.clear(); dfs_resi(u, cen, 1, w); for(auto c : cuvaj){ // cout << c.fi << " " << c.se << endl; kol[c.fi] = min(kol[c.fi], c.se); pom.pb(c.fi); } // cout << endl; } for(auto c : pom)kol[c] = inf; 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; ff(i,1,5 * maxn - 1)kol[i] = inf; decompose(0, -2); 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}); // } // ff(i,1,5 * maxn - 1)kol[i] = inf; // 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 **/