#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "race.h" using namespace std; #define fi first #define se second #define ll long long bool dead[200005]; int s[200005],n,k; ll ans=LLONG_MAX; vector<vector<pair<int,int> > > vec; map<ll,multiset<int> > mymap; map<ll,int> best; int dfs(int node,int p,bool flag=0,int d=0,ll h=0){ s[node]=1; if(flag)mymap[h].insert(d); for(auto it:vec[node]) if(it.fi!=p&&!dead[it.fi]) s[node]+=dfs(it.fi,node,flag,d+1,h+it.se); return s[node]; } void remove(int node,int p,int d,ll h){ if(best.count(h))best[h]=min(best[h],d); else best[h]=d; auto it=mymap[h].find(d); mymap[h].erase(it); if(mymap[h].empty())mymap.erase(h); for(auto it:vec[node]) if(it.fi!=p&&!dead[it.fi]) remove(it.fi,node,d+1,h+it.se); } int find_cetroid(int node,int p){ for(auto it:vec[node]) if(it.fi!=p&&!dead[it.fi]&&s[it.fi]>(n/2)) return find_cetroid(it.fi,node); return node; } void solve(int node){ n=dfs(node,node); //cerr<<n<<","<<node<<"\n"; int r=find_cetroid(node,node); //cerr<<"centroid: "<<r<<"\n"; mymap.clear(); dfs(r,r,1); /*cerr<<"sz(mymap): "<<mymap.size()<<"\n"; for(auto it:mymap){ cerr<<"dist: "<<it.fi<<"\n"; for(auto it2:it.se) cerr<<it2<<" "; cout<<"\n"; }*/ for(auto it:vec[r]){ if(dead[it.fi])continue; remove(it.fi,r,1,it.se); for(auto it3:best){ if(it3.fi>k)break; //cerr<<"it3.fi : "<<it3.fi<<"\n"; //cerr<<"k-it3.fi: "<<k-it3.fi<<"\n"; if(mymap.count(k-it3.fi))ans=min(ans,(ll)*(mymap[k-it3.fi].begin())+it3.se); } //cerr<<"subtree : "<<it.fi<<"\n"; //cerr<<"ans : "<<ans<<"\n"; for(auto it3:best) mymap[it3.fi].insert(it3.se); best.clear(); } dead[r]=1; for(auto it:vec[r]) if(!dead[it.fi]) solve(it.fi); } int best_path(int N, int K, int H[][2], int L[]) { k=K; vec.resize(N); for (int i = 0; i < N-1; ++i) { vec[H[i][0]].push_back({H[i][1],L[i]}); vec[H[i][1]].push_back({H[i][0],L[i]}); } solve(0); return ((ans==LLONG_MAX)?(-1):ans); }