#include <bits/stdc++.h>
#include "race.h"
using namespace std;
// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;
typedef pair<ll, ll> pll;
int ret;
int n, k;
vector<pii> edges[200000];
bool centroidseen[200000];
int treesz[200000];
void dfsfromcentroid(int curr, int par, map<int, int>& dp, int dist, int roads) {
if(dist > k) return;
if(!dp.count(dist)) dp[dist] = roads;
else dp[dist] = min(dp[dist], roads);
for(pii out: edges[curr]) {
if(centroidseen[out.first] || out.first == par) continue;
dfsfromcentroid(out.first, curr, dp, dist + out.second, roads + 1);
}
}
void dfsforsz(int curr, int par) {
treesz[curr] = 1;
for(pii out: edges[curr]) {
int child = out.first;
if(centroidseen[child] || child == par) continue;
dfsforsz(child, curr);
treesz[curr] += treesz[child];
}
}
void centroiddecomp(int curr) {
if(centroidseen[curr]) return;
dfsforsz(curr, -1);
int totalsz = treesz[curr];
int centroidpar = -1;
while(true) {
int biggestchildsz = -1;
int biggestchild = -1;
for(pii out: edges[curr]) {
int cand = out.first;
if(centroidseen[cand] || cand == centroidpar) continue;
if(treesz[cand] > biggestchildsz) {
biggestchildsz = treesz[cand];
biggestchild = cand;
}
}
if(2 * biggestchildsz > totalsz) {
centroidpar = curr;
curr = biggestchild;
}
else {
break;
}
}
// curr is the centroid
{
map<int, int> dp;
for(pii edge: edges[curr]) {
if(centroidseen[edge.first]) continue;
map<int, int> childdp;
dfsfromcentroid(edge.first, curr, childdp, edge.second, 1);
for(auto out: childdp) {
if(out.first == k) ret = min(ret, out.second);
if(dp.count(k - out.first)) ret = min(ret, out.second + dp[k - out.first]);
}
for(auto out: childdp) {
if(!dp.count(out.first)) dp[out.first] = out.second;
else dp[out.first] = min(dp[out.first], out.second);
}
}
}
centroidseen[curr] = true;
for(pii out: edges[curr]) centroiddecomp(out.first);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
ret = n+1;
for(int i = 0; i < n-1; i++) {
edges[H[i][0]].emplace_back(H[i][1], L[i]);
edges[H[i][1]].emplace_back(H[i][0], L[i]);
}
centroiddecomp(0);
if(ret > n) ret = -1;
return ret;
}
