#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200010
int n,k;
vector<pair<int,int>> adj[MAXN];
int siz[MAXN];
bool uklonjeno[MAXN];
map<int,int> mapa;
int ans=INT_MAX;
int subtree_size(int node,int pret)
{
siz[node]=1;
int s=adj[node].size();
for (int i=0;i<s;i++)
{
int sled=adj[node][i].first;
if (sled==pret) continue;
if (uklonjeno[sled]==true) continue;
siz[node]+=subtree_size(sled,node);
}
return siz[node];
}
int get_centroid(int node,int pret,int velicina)
{
int s=adj[node].size();
for (int i=0;i<s;i++)
{
int sled=adj[node][i].first;
if (sled==pret) continue;
if (uklonjeno[sled]==true) continue;
if (siz[sled]*2>velicina) return get_centroid(sled,node,velicina);
}
return node;
}
void racunamo(int node,int pret,bool stanje,int dubina,int depth)
{
if (dubina>k) return;
if (stanje==false)
{
int val=k-dubina;
if (mapa.find(val)!=mapa.end()) ans=min(ans,depth+mapa[val]);
}
else
{
if (mapa.find(dubina)==mapa.end()) mapa[dubina]=depth;
else mapa[dubina]=min(mapa[dubina],depth);
}
int s=adj[node].size();
for (int i=0;i<s;i++)
{
int sled=adj[node][i].first;
int tezina=adj[node][i].second;
if (sled==pret) continue;
if (uklonjeno[sled]==true) continue;
racunamo(sled,node,stanje,dubina+tezina,depth+1);
}
}
void centroid_decomposition(int node)
{
subtree_size(node,-1);
int centroida=get_centroid(node,-1,siz[node]);
uklonjeno[centroida]=true;
int s=adj[centroida].size();
for (int i=0;i<s;i++)
{
int sled=adj[centroida][i].first;
int tezina=adj[centroida][i].second;
if (uklonjeno[sled]==true) continue;
racunamo(sled,centroida,false,tezina,1);
racunamo(sled,centroida,true,tezina,1);
}
if (mapa.find(k)!=mapa.end()) ans=min(ans,mapa[k]);
mapa.clear();
for (int i=0;i<s;i++)
{
int sled=adj[centroida][i].first;
if (uklonjeno[sled]==true) continue;
centroid_decomposition(sled);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N,k=K;
for (int i=0;i<n-1;i++)
{
int a=H[i][0],b=H[i][1];
int len=L[i];
adj[a].push_back({b,len});
adj[b].push_back({a,len});
}
centroid_decomposition(0);
if (ans==INT_MAX) return -1;
else return ans;
};
