#include "race.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
using ull = long long;
const int INF = 0x3f3f3f3f;
const int MX = 200005;
int ans = INF, k, s[MX], used[300005], c;
vector<pair<int, int>> adj[MX], t;
vector<int> val(1000005, INF);
bitset<MX> r;
int dfs(int u, int p) {
s[u] = 1;
for(auto &v : adj[u])
if(v.first!=p&&!r[v.first])
s[u] += dfs(v.first, u);
return s[u];
}
void dfs2(int u, int p, int l, int c) {
if(k-l<0) return;
if(val[k-l]!=INF) ans = min(ans, val[k-l]+c);
t.push_back({l, c});
for(auto &v : adj[u])
if(v.first!=p&&!r[v.first])
dfs2(v.first, u, l+v.second, c+1);
}
int get_centroid(int u, int p, int ms) {
for(auto &v : adj[u])
if(v.first!=p&&!r[v.first]&&s[v.first]*2>ms)
return get_centroid(v.first, u, ms);
return u;
}
void centroid(int u = 1) {
int C = get_centroid(u, u, dfs(u, u));
r[C] = 1;
c = 0;
for(auto &x : adj[C]) {
if(!r[x.first]) {
t.clear();
dfs2(x.first, C, x.second, 1);
for(auto &i : t) {
if(i.first<=k) {
val[i.first] = min(val[i.first], i.second);
used[++c] = i.first;
}
}
}
}
ans = min(ans, val[k]);
for(; c; c--)
val[used[c]] = INF;
for(auto v : adj[C])
if(!r[v.first])
centroid(v.first);
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N-1; ++i) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
centroid();
if(ans==INF) ans = -1;
return ans;
}
