#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 merge(map<int, int>& dp, map<int, int>& childdp, int w) {
// query
if(sz(childdp) < sz(dp)) {
for(auto out: childdp) {
int want = k - out.first - w;
if(dp.count(want)) ret = min(ret, out.second + dp[want] + 1);
}
}
else {
for(auto out: dp) {
int want = k - out.first - w;
if(childdp.count(want)) ret = min(ret, out.second + childdp[want] + 1);
}
}
map<int, int> clean;
for(auto out: childdp) {
if(out.first + w <= k) clean[out.first+w] = out.second + 1;
}
// merge
if(sz(dp) < sz(clean)) dp.swap(clean);
for(auto out: clean) {
if(!dp.count(out.first)) dp[out.first] = out.second;
else dp[out.first] = min(dp[out.first], out.second);
}
}
void dfsforans(int curr, int par, map<int, int>& dp) {
for(pii out: edges[curr]) {
if(centroidseen[out.first] || par == out.first) continue;
map<int, int> childdp;
dfsforans(out.first, curr, childdp);
if(childdp.count(k)) ret = min(ret, childdp[k]);
merge(dp, childdp, out.second);
}
dp[0] = 0;
}
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;
dfsforans(curr, -1, dp);
}
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;
}
