#include "race.h" #include <stdio.h> #include <vector> using namespace std; #define pb push_back #define mp make_pair void ckmx(int&a,int b){a=max(a,b);} void ckmn(int&a,int b){a=min(a,b);} int min(int a,int b){return a>b?b:a;} const int N=200050; const int M=1000050; const int inf=1e9; vector<pair<int,int>> E[N]; void AddEdge(int u,int v,int w){E[u].pb(mp(v,w));E[v].pb(mp(u,w));} int k; int sz[N]; bool was[N]; void DFS(int u,int p,int& n){ n++;sz[u]=1; for(int i=0;i<(int)E[u].size();i++)if(!was[E[u][i].first]&&E[u][i].first!=p){ DFS(E[u][i].first,u,n);sz[u]+=sz[E[u][i].first]; } } int Find(int u,int p,int n){ for(int i=0;i<(int)E[u].size();i++){ int v=E[u][i].first; if(!was[v]&&v!=p&&sz[v]>n/2)return Find(v,u,n); } return u; } int FindCentroid(int u){int n=0;DFS(u,u,n);return Find(u,u,n);} vector<pair<int,int>> all,tmp; int ans=inf,mn[M]; void Solve(int u,int p,int dep,int len){ if(dep>k)return; all.pb({dep,len}); tmp.pb({dep,len}); ans=min(ans,len+mn[k-dep]); for(int i=0;i<(int)E[u].size();i++){ int v=E[u][i].first,w=E[u][i].second; if(!was[v]&&v!=p)Solve(v,u,dep+w,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(i=0;i<(int)tmp.size();i++)mn[tmp[i].first]=inf; tmp.clear(); for(i=0;i<(int)E[u].size();i++){ int v=E[u][i].first; if(!was[v])Decompose(v); } } int best_path(int N,int K,int H[][2],int L[]){ //return -1; int i,n=N;k=K; for(i=0;i<n-1;i++)AddEdge(H[i][0]+1,H[i][1]+1,L[i]); for(i=0;i<=k;i++)mn[i]=inf; Decompose(1); if(ans==inf)return -1; else return ans; }