#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define pb push_back
const ll MAXN = 2e5 + 5;
const ll INF = 1e6 + 5;
vector<array<ll, 2>> g[MAXN];
ll K, ans = INF, tsize[MAXN], buck[INF], actual;
bool vis[MAXN];
void calc_tsize(ll u, ll p = 0) {
tsize[u] = 1;
for (auto &it : g[u])
if (it[0] != p && !vis[it[0]]) { calc_tsize(it[0], u); tsize[u] += tsize[it[0]]; }
}
ll centroid(ll u, ll p = 0) {
for (auto &it : g[u])
if (!vis[it[0]] && it[0] != p && 2*tsize[it[0]] > actual) return centroid(it[0], u);
return u;
}
void calc(ll u, ll p, ll s, ll h = 1) {
if (s == K) ans = min(ans, h);
if (s > K) return;
if (buck[K - s]) ans = min(ans, h + buck[K - s]);
for (auto &it : g[u])
if (!vis[it[0]] && it[0] != p) calc(it[0], u, s + it[1], h + 1);
}
void update(ll u, ll p, ll s, ll h = 1) {
if (s > K) return;
if (!buck[s]) buck[s] = h;
buck[s] = min(buck[s], h);
for (auto &it : g[u])
if (!vis[it[0]] && it[0] != p) update(it[0], u, s + it[1], h + 1);
}
void erase(ll u, ll p = 0, ll s = 0) {
if (s > K) return;
buck[s] = 0;
for (auto &it : g[u])
if (!vis[it[0]] && it[0] != p) erase(it[0], u, s + it[1]);
}
void solve(ll u = 1) {
calc_tsize(u); actual = tsize[u];
u = centroid(u); vis[u] = true;
for (auto &it : g[u]) {
if (vis[it[0]]) continue;
calc(it[0], u, it[1]);
update(it[0], u, it[1]);
}
erase(u);
for (auto &it : g[u])
if (!vis[it[0]]) solve(it[0]);
}
int best_path(int N, int k, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
H[i][0]++; H[i][1]++;
g[H[i][0]].pb(array<ll, 2> { H[i][1], L[i] });
g[H[i][1]].pb(array<ll, 2> { H[i][0], L[i] });
}
K = k;
solve();
if (ans == INF) ans = -1;
return ans;
}
/*
int main() {
int N, K; cin >> N >> K;
int H[N - 1][2], L[N - 1];
for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1];
for (int i = 0; i < N - 1; i++) cin >> L[i];
cout << best_path(N, K, H, L);
}
*/
