// I wonder how much faster it is (cos this one passes on train https://train.nzoi.org.nz/submissions/166506 while my other OJ AC doesn't)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
// #include "race.h"
// centroid decomp & dp => O(N * log^2 N)
int N, K, res = INT_MAX;
vector<vector<pair<int,int>>> adj;
vector<int> sz;
vector<bool> del;
int dfsSZ(int n, int p) {
sz[n] = 1;
for(auto [c, l]: adj[n]) {
if (c == p || del[c]) continue;
sz[n] += dfsSZ(c, n);
}
return sz[n];
}
int dfsCEN(int n, int p, int treeSZ) {
for(auto [c, l]: adj[n]) {
if (c == p || del[c] || sz[c] * 2 <= treeSZ) continue;
return dfsCEN(c, n, treeSZ);
}
return n;
}
void solve(int n, int p, int dist, int dep, unordered_map<int,int> &dp) {
if (dist > K) return ;
if (dp.find(K-dist) != dp.end()) res = min(res, dp[K-dist] + dep);
if (dist == K) {res = min(res, dep); return ;}
for(auto [c, l]: adj[n]) {
if (c == p || del[c]) continue;
solve(c, n, dist+l, dep+1, dp);
}
}
void solve2(int n, int p, int dist, int dep, unordered_map<int,int> &dp) {
if (dp.find(dist) == dp.end() || dp[dist] > dep) dp[dist] = dep;
if (dist >= K) return ;
for(auto [c, l]: adj[n]) {
if (c == p || del[c]) continue;
solve2(c, n, dist+l, dep+1, dp);
}
}
void build(int n) {
int cen = dfsCEN(n, n, dfsSZ(n, n));
// for every centroid, there will be at most N' values (where N' = the number of nodes in the centroid)
// subset sum dp - in the solve on line 39 and solve2 on line 47
unordered_map<int,int> dp;
for(auto [c, l]: adj[cen]) {
if (del[c]) continue;
solve(c, cen, l, 1, dp);
solve2(c, cen, l, 1, dp);
}
del[cen] = true;
for(auto [c, l]: adj[cen]) {
if (del[c]) continue;
build(c);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
::N = N, ::K = K;
adj.resize(N), sz.resize(N), del.resize(N);
FOR(i, N-1) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
build(0);
return (res == INT_MAX ? -1 : res);
}
