#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
const int MAXN = 200000 + 10, MAXK = 1000000 + 10, INF = 100000000;
vector<lli> g[MAXN], p[MAXN];
lli marc[MAXK], lastSave[MAXK], removed[MAXN], sub[MAXN];
lli ans = INF, cnt, globalK;
lli readMarc(lli pos){
if(pos < 0 || pos > MAXK) return INF;
if(lastSave[pos] == cnt) return marc[pos];
else return INF;
}
void writeMarc(lli pos, lli val){
marc[pos] = val; lastSave[pos] = cnt;
}
void calcSub(lli v, lli f){
sub[v] = 1;
for(lli i = 0;i<(lli)g[v].size();i++){
lli viz = g[v][i];
if(viz == f || removed[viz] == 1) continue;
calcSub(viz, v);
sub[v] += sub[viz];
}
return;
}
lli findCentroid(lli v, lli f){
lli centroid = v;
for(lli i = 0;i<(lli)g[v].size();i++){
lli viz = g[v][i];
if(removed[viz] == 1 || viz == f) continue;
if(sub[viz] > sub[v]/2){
sub[v] -= sub[viz];
sub[viz] += sub[v];
centroid = findCentroid(viz, v);
}
}
return centroid;
}
void computeSubtree(lli v, lli f, lli dist, lli edgeCount){
if(dist == globalK){
ans = min(ans, edgeCount);
return;
}
lli possible = readMarc(globalK - dist);
if(possible != INF){
ans = min(ans, possible + edgeCount);
}
for(lli i = 0;i<(lli)g[v].size();i++){
lli viz = g[v][i];
if(viz == f || removed[viz] == 1) continue;
computeSubtree(viz, v, dist + p[v][i], edgeCount + 1);
}
if(dist <= MAXK && readMarc(dist) > edgeCount) writeMarc(dist, edgeCount);
}
void doTree(lli v){
calcSub(v, -1);
lli centroid = findCentroid(v, -1);
removed[centroid] = 1;
if(sub[centroid] == 1) return;
cnt++;
for(lli i = 0;i<(lli)g[centroid].size();i++){
lli viz = g[centroid][i];
if(removed[viz] == 1) continue;
computeSubtree(viz, centroid, p[centroid][i], 1);
}
for(lli i = 0;i<(lli)g[centroid].size();i++){
lli viz = g[centroid][i];
if(removed[viz] == 1) continue;
doTree(viz);
}
}
int best_path(int N, int K, int H[][2], int L[]){
globalK = K;
for(lli i = 0;i<N-1;i++){
lli a = H[i][0], b = H[i][1];
g[a].push_back(b); g[b].push_back(a);
p[a].push_back(L[i]); p[b].push_back(L[i]);
}
calcSub(0,-1);
doTree(0);
if(ans == INF) return -1;
return ans;
}
