#include "race.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct grana{
int gde;
ll cena;
}pp;
vector<grana> stablo[200005];
int N,K,res=1e9;
const int INF=1e9;
int kol[200005],najb[1000005],p1,p2;
ll duzina[200005],puta[200005];
bool block[200005];
ll min(int a,ll b){
if(a<b)
return a;
return b;
}
int rootuj(int gde,int pret){
if(block[gde])
return 0;
kol[gde]=1;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i].gde!=pret)
kol[gde]+=rootuj(stablo[gde][i].gde,gde);
return kol[gde];
}
int nadji(int gde,int pret,int pola){
int sled=-1;
for(int i=0;i<stablo[gde].size();i++){
if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret)
continue;
if(kol[stablo[gde][i].gde]>pola)
sled=kol[stablo[gde][i].gde];
}
if(sled==-1)
return gde;
return nadji(sled,gde,pola);
}
vector<int> V;
void racunaj(int gde,int pret,ll dist,int put){
duzina[gde]=dist;
puta[gde]=put;
V.push_back(gde);
for(int i=0;i<stablo[gde].size();i++){
if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret)
continue;
racunaj(stablo[gde][i].gde,gde,dist+stablo[gde][i].cena,put+1);
}
return;
}
void rek(int gde){
rootuj(gde,gde);
int c=nadji(gde,gde,kol[gde]/2+3);
V.clear();
racunaj(c,c,0,0);
p1=INF;
p2=INF;
for(int i=0;i<V.size();i++){
if(duzina[V[i]]>K)
continue;
if(duzina[V[i]]==K/2){
if(puta[V[i]]<p1){
p2=p1;
p1=puta[V[i]];
}
else
p2=min(p2,puta[V[i]]);
}
else
najb[duzina[V[i]]]=min(najb[duzina[V[i]]],puta[V[i]]);
}
res=min(res,p1+p2);
for(int i=0;i<V.size();i++)
if(duzina[V[i]]!=K/2 and duzina[V[i]]<=K)
res=min(res,najb[duzina[V[i]]]+najb[K-duzina[V[i]]]);
for(int i=0;i<V.size();i++){
if(duzina[V[i]]>K)
continue;
najb[duzina[V[i]]]=INF;
}
block[c]=true;
kol[c]=INF;
for(int i=0;i<stablo[c].size();i++)
if(!block[stablo[c][i].gde])
rek(stablo[c][i].gde);
return;
}
int best_path(int n,int k,int h[][2],int l[]){
N=n;
K=k;
for(int i=0;i<N;i++){
h[i][0]++;
h[i][1]++;
pp.cena=l[i];
pp.gde=h[i][1];
stablo[h[i][0]].push_back(pp);
pp.gde=h[i][0];
stablo[h[i][1]].push_back(pp);
}
for(int i=0;i<=K;i++)
najb[i]=INF;
rek(1);
if(res==1e9)
return -1;
return res;
}
