#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define ll long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())
#define all(a) (a).begin(), a.end()
#define dbg(v) \
cout << "Line(" << _LINE << ") -> " << #v << " = " << (v) << endl;
int const INF = 0x3f3f3f3f;
ll const LINF = 0x3f3f3f3f3f3f3f3fll;
const int maxn = 2e5+10;
vector<PI> adj[maxn];
int subsize[maxn];
bool isremoved[maxn];
int get_subsize(int x, int prev=-1){
subsize[x] = 1;
for (auto [nex, w] : adj[x]){
if (nex == prev || isremoved[nex]) continue;
subsize[x] += get_subsize(nex, x);
}
return subsize[x];
}
int get_centroid(int x, int tsize, int prev=-1){
for (auto [nex, w] : adj[x]){
if (nex == prev || isremoved[nex]) continue;
if (subsize[nex] * 2 > tsize) return get_centroid(nex, tsize, x);
}
return x;
}
const int maxk = 1e6+10;
int dp[maxk];
int k;
int maxdep;
void dfs1(int x, int cent, int d, int cnt=1, int prev=-1){
if (d > k) return;
for (auto [nex, w] : adj[x]){
if (nex == prev || isremoved[nex]) continue;
dfs1(nex, cent, d+w, cnt+1, x);
}
maxdep = max(maxdep, d);
dp[d] = min(dp[d], cnt);
}
int ans;
void dfs2(int x, int cent, int d, int cnt=1, int prev=-1){
if (d > k) return;
for (auto [nex, w] : adj[x]){
if (nex == prev || isremoved[nex]) continue;
dfs2(nex, cent, d+w, cnt+1, x);
}
if (k-d <= maxdep) ans = min(ans, cnt + dp[k-d]);
}
void build_decomp(int x){
int cent = get_centroid(x, get_subsize(x));
isremoved[cent] = true;
for (int i = 0; i <= maxdep; ++i) dp[i] = INF;
maxdep = 0;
dp[0] = 0;
for (auto [nex, w] : adj[cent]){
if (!isremoved[nex]){
dfs2(nex, cent, w);
dfs1(nex, cent, w);
}
}
for (auto [nex, w] : adj[cent]){
if (isremoved[nex]) continue;
build_decomp(nex);
}
}
int best_path(int n, int K, int h[][2], int l[]){
k = K;
maxdep = k;
ans = INF;
for (int i = 0; i < n-1; ++i){
adj[h[i][0]].pb({h[i][1], l[i]});
adj[h[i][1]].pb({h[i][0], l[i]});
}
build_decomp(0);
if (ans < INF) return ans;
return -1;
}
