#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
// global
int ans = 1e9, n, k;
vector<pair<int,long long> > v[200005];
// centroid
int sz[200005];
bool visited[200005];
// query & update
int has[1000005];
void query(int nw,int fa,int dep,long long total)
{
if(total > k) return ;
if(has[k - total] != 1e9)
ans = min(ans, dep + has[k - total]);
for(auto go: v[nw])
if(go.f != fa && !visited[go.f])
query(go.f, nw, dep + 1, total + go.s);
}
void update(int nw,int fa,int dep, long long total)
{
if(total > k) return ;
has[total] = min(has[total], dep);
for(auto go: v[nw])
if(go.f != fa && !visited[go.f])
query(go.f, nw, dep + 1, total + go.s);
}
int re_size(int nw,int fa)
{
sz[nw] = 1;
for(auto go: v[nw])
if(go.f != fa && !visited[go.f])
sz[nw] += re_size(go.f,nw);
return sz[nw];
}
int fi_cen(int nw,int fa,int sum)
{
for(auto go: v[nw])
if(go.f != fa && !visited[go.f] && sz[go.f] > sum/2)
return fi_cen(go.f,nw,sum);
return nw;
}
void centroid_decomp(int nw)
{
int cen = fi_cen(nw, -1, re_size(nw, -1));
visited[cen] = true;
has[0] = 0;
for(int i = 1; i <= k; i++)
has[i] = 1e9;
for(auto go: v[cen])
{
if(!visited[go.f])
{
query(go.f, cen, 1, go.s);
update(go.f, cen, 1, go.s);
}
}
for(auto go: v[cen])
if(!visited[go.f])
centroid_decomp(go.f);
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for(int i = 0; i < n - 1; i++)
{
v[H[i][0]].emplace_back(H[i][1], L[i]);
v[H[i][1]].emplace_back(H[i][0], L[i]);
}
centroid_decomp(0);
if(ans == 1e9)
return -1;
return ans;
}
// int a,b;
// int send[200005][2],send2[200005];
// int main()
// {
// scanf("%d %d",&a,&b);
// for(int i = 0; i < a - 1; i++)
// scanf("%d %d %d",&send[i][0],&send[i][1],&send2[i]);
// printf("%d",best_path(a, b, send, send2));
// return 0;
// }
