#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1
const int SN = 1e6 + 7;
const int TN = 4 * SN;
const int oo = 1e9;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
int cn, w[SN], mn[SN], ans, s, n, k;
bool vis[SN];
vii v[SN];
vi f;
void dfs (int o, int p) {
// cout << o <<' ';
w[o] = 0;
for (auto c : v[o]) {
if (c.ff == p || vis[c.ff])
continue;
dfs (c.ff, o);
w[o] += w[c.ff];
}
w[o]++;
}
int find (int o, int p) {
for (auto c : v[o]) {
if (c.ff == p || vis[c.ff])
continue;
if (w[c.ff] * 2 > w[cn]) {
return find(c.ff, o);
}
}
return o;
}
void dfs2 (int o, int p, int d) {
if (s > k) return;
if (k == s) {
ans = min(ans, d);
return;
}
if (mn[k - s]) {
ans = min(ans, mn[k - s] + d);
}
for (auto c : v[o]) {
if (c.ff == p || vis[c.ff])
continue;
s += c.ss;
dfs2(c.ff, o, d + 1);
s -= c.ss;
}
}
void dfs3 (int o, int p, int d) {
if (s > k) return;
if (mn[s]) mn[s] = min(mn[s], d);
else {
f.pb(s);
mn[s] = d;
}
for (auto c : v[o]) {
if (c.ff == p || vis[c.ff])
continue;
s += c.ss;
dfs3 (c.ff, o, d + 1);
s -= c.ss;
}
}
void solve () {
for (auto c : v[cn]) {
if (vis[c.ff])
continue;
s = c.ss;
dfs2(c.ff, cn, 1);
s = c.ss;
dfs3(c.ff, cn, 1);
}
}
void dfs4(int o) {
vis[o] = 1;
for (auto c : v[o]) {
if (vis[c.ff])
continue;
for (auto x : f)
mn[x] = 0;
f.clear();
// cout << o << ": ";
dfs(c.ff, c.ff);
cn = c.ff;
int next = find(c.ff, c.ff);
// cout << ' ' << next << '\n';
cn = next;
solve();
vis[next] = 1;
dfs4(next);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
ans = oo;
for (int i = 0; i < n - 1; i++) {
v[H[i][0]].pb({H[i][1], L[i]});
v[H[i][1]].pb({H[i][0], L[i]});
}
dfs(0, 0);
cn = find(0, 0);
solve();
dfs4(cn);
if (ans == oo) return -1;
return ans;
}
