#include <bits/extc++.h>
#include "race.h"
using namespace std;
using namespace __gnu_pbds;
#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)
template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;
constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------
const int N = 2e5+5;
const int K = 1e6+5;
int n, k, ans = inf, sub[N];
vpi adj[N];
bitset<N> r;
struct evan {
int a[K];
vi un;
evan() {
memset(a, 0x3f, sizeof a);
a[0] = 0;
}
void set(int i, int x){
un.pb(i);
a[i] = x;
}
int get(int i){
return a[i];
}
void clear(){
for(int i: un)
a[i] = inf;
a[0] = 0;
un.clear();
}
} a;
void dfs(int v, int p){
if(r[v]) {
sub[v] = 0;
return;
}
sub[v] = 1;
for(auto[u, w]: adj[v]){
if(u==p)
continue;
dfs(u, v);
sub[v] += sub[u];
}
}
int get_centroid(int v, int p, int sz){
for(auto[u, _]: adj[v])
if(!r[u]&&u!=p&&sub[u]*2>sz)
return get_centroid(u, v, sz);
return v;
}
void upd_ans(int v, int p, ll dis, int dep){
if(r[v]||dis>k)
return;
ans = min(ans, a.get(k-dis)+dep);
for(auto[u, w]: adj[v])
if(u!=p)
upd_ans(u, v, dis+w, dep+1);
}
void upd_a(int v, int p, ll dis, int dep){
if(r[v]||dis>k)
return;
a.set(dis, min(a.get(dis), dep));
for(auto[u, w]: adj[v])
if(u!=p)
upd_a(u, v, dis+w, dep+1);
}
void solve(int v){
if(r[v])
return;
dfs(v, -1);
int c = get_centroid(v, -1, sub[v]);
r[c] = 1;
a.clear();
for(auto[u, w]: adj[c]){
upd_ans(u, c, w, 1);
upd_a(u, c, w, 1);
}
for(auto[u, _]: adj[c])
solve(u);
}
int best_path(int _n, int _k, int h[][2], int l[]) {
n = _n;
k = _k;
for(int i = 0; i +1 < n; ++i) {
adj[h[i][0]].eb(h[i][1], l[i]);
adj[h[i][1]].eb(h[i][0], l[i]);
}
solve(0);
if(ans==inf)
return -1;
return ans;
}
