#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=stablo[gde][i].gde;
}
if(sled==-1)
return gde;
return nadji(sled,gde,pola);
}
vector<int> V,W;
void racunaj(int gde,int pret,ll dist,int put){
duzina[gde]=dist;
puta[gde]=put;
// cout<<"DFS "<<gde<<" "<<pret<<" "<<put<<" "<<dist<<endl;
if(dist<=K)
res=min(res,put+najb[K-dist]);
if(dist==K)
res=min(res,put);
V.push_back(gde);
W.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;
if(gde==pret)
W.clear();
racunaj(stablo[gde][i].gde,gde,dist+stablo[gde][i].cena,put+1);
if(gde==pret)
for(int i=0;i<W.size();i++)
if(duzina[W[i]]<=K)
najb[duzina[W[i]]]=min(najb[duzina[W[i]]],puta[W[i]]);
}
return;
}
void rek(int gde){
rootuj(gde,gde);
int c=nadji(gde,gde,kol[gde]/2+3);
V.clear();
racunaj(c,c,0,0);
/*
cout<<"CENTROID JE "<<c<<endl;
for(int i=0;i<V.size();i++)
cout<<V[i]<<": "<<puta[V[i]]<<" "<<duzina[V[i]]<<endl;
cout<<endl;
cout<<"RES= "<<res<<endl;*/
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-1;i++){
h[i][0]++;
h[i][1]++;
pp.cena=l[i];
pp.gde=h[i][1];
stablo[h[i][0]].push_back(pp);
//cout<<h[i][0]<<" "<<h[i][1]<<endl;
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;
}
