#include "race.h" #include <bits/stdc++.h> using namespace std; #define pb push_back int ckmx(int&a,int b){a=max(a,b);} int ckmn(int&a,int b){a=min(a,b);} const int N=200050; const int inf=1e9; int ans=inf,sz[N],K,mn[5*N]; vector<pair<int,int>> E[N]; bool was[N]; int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];} int Find(int u,int p,int n){for(auto e:E[u])if(e.first!=p&&!was[e.first]&&sz[e.first]*2>n)return Find(e.first,u,n);return u;} int FindCentroid(int u){DFS(u,u);return Find(u,u,sz[u]);} vector<pair<int,int>> all,tmp; void Solve(int u,int p,int dep,int len){ if(dep>K)return; //printf("%i %i %i %i\n",u,p,dep,len); all.pb({dep,len}); tmp.pb({dep,len}); if(mn[K-dep]!=inf)ans=min(ans,len+mn[K-dep]); for(auto e:E[u])if(!was[e.first]&&e.first!=p)Solve(e.first,u,dep+e.second,len+1); } void Decompose(int u){ u=FindCentroid(u); was[u]=1;mn[0]=0; tmp.pb({0,0}); int i,j; for(i=0;i<(int)E[u].size();i++){ int v=E[u][i].first,w=E[u][i].second; if(!was[v]){ Solve(v,u,w,1); for(j=0;j<(int)all.size();j++)ckmn(mn[all[j].first],all[j].second); all.clear(); } } for(auto c:tmp)mn[c.first]=inf; tmp.clear(); for(auto e:E[u])if(!was[e.first])Decompose(e.first); } int best_path(int n,int k,int h[][2],int l[]){ //return -1; int i;K=k; for(i=0;i<n-1;i++){ E[h[i][0]+1].pb(make_pair(h[i][1]+1,l[i])); E[h[i][1]+1].pb(make_pair(h[i][0]+1,l[i])); } for(i=0;i<=k;i++)mn[i]=inf; Decompose(1); if(ans==inf)return -1; else return ans; }

race.cpp: In function 'int ckmx(int&, int)':
race.cpp:5:34: warning: no return statement in function returning non-void [-Wreturn-type]
    5 | int ckmx(int&a,int b){a=max(a,b);}
      |                                  ^
race.cpp: In function 'int ckmn(int&, int)':
race.cpp:6:34: warning: no return statement in function returning non-void [-Wreturn-type]
    6 | int ckmn(int&a,int b){a=min(a,b);}
      |                                  ^
race.cpp: In function 'int DFS(int, int)':
race.cpp:12:109: warning: no return statement in function returning non-void [-Wreturn-type]
   12 | int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];}
      |                                                                                                             ^