#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll M = 200'010; ll n,kk, inf=1e7; ll ans = inf; vector<vector<pair<ll, ll>>> g(M); vector<ll> par(M), sajz(M), is_off(M), depth(M); void sajz_dfs(ll v, ll p) { sajz[v] = 1; par[v] = p; for(auto[u,k] : g[v]) { if(is_off[u] || u==p) continue; depth[u] = depth[v] + 1; sajz_dfs(u,v); sajz[v] += sajz[u]; } } ll find_centroid(ll v, ll ts) { for(auto[u,k] : g[v]) { if(is_off[u]) continue; if(u==par[v]) { if(ts-sajz[v] > ts/2) return find_centroid(u,ts); } else { if(sajz[u] > ts/2) return find_centroid(u,ts); } } return v; } map<ll, ll> mapa1, mapa2; void calc_dfs(ll v, ll p, ll d) { if(mapa1.find(d)==mapa1.end()) mapa1[d] = depth[v]; else mapa1[d] = min(mapa1[d], depth[v]); if(mapa2.find(kk-d)!=mapa2.end()) ans = min(ans, mapa2[kk-d] + mapa1[d]); for(auto[u,k] : g[v]) { if(u==p || is_off[u]) continue; calc_dfs(u,v,d+k); } } void upd_dfs(ll v, ll p, ll d) { if(mapa2.find(d)==mapa2.end()) mapa2[d] = mapa1[d]; else mapa2[d] = min(mapa2[d], mapa1[d]); for(auto[u,k] : g[v]) { if(u==p || is_off[u]) continue; upd_dfs(u,v,d+k); } } void centroid_decomp(ll v) { sajz_dfs(v,v); ll ctr = find_centroid(v,sajz[v]); depth[ctr] = 0; sajz_dfs(ctr,ctr); mapa2[0] = 0; for(auto[u,k] : g[ctr]) { if(is_off[u]) continue; calc_dfs(u,ctr,k); upd_dfs(u,ctr,k); } mapa1.clear(); mapa2.clear(); is_off[ctr] = 1; for(auto[u,k] : g[ctr]) if(!is_off[u]) centroid_decomp(u); } int best_path(int N, int K, int H[][2], int L[]) { n=N; kk=K; for(ll i=0; i<n-1; ++i) { ll a = H[i][0]; ll b = H[i][1]; ll c = L[i]; g[a].push_back({b,c}); g[b].push_back({a,c}); } centroid_decomp(0); if(ans==inf) return -1; return ans; }