// The capital, vodka, the Soviet bear!
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fi first
#define se second
void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}
const ll maxN = 2e5 + 5, inf64 = 1e18, maxA = 1e6 + 5;
ll n, k, sz [maxN], f [maxA], ans;
bool del [maxN];
vector <ll> vec;
vector <pll> adj [maxN];
ll dfs (ll x, ll par) {
sz [x] = 1;
for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
sz [x] += dfs (i. fi, x);
}
return sz [x];
}
ll finCen (ll x, ll par, ll cnt) {
for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
if (sz [i. fi] * 2 >= cnt) return finCen (i. fi, x, cnt);
}
return x;
}
void get (ll x, ll par, ll dis, ll numNode) {
if (k >= dis) mini (ans, f [k - dis] + numNode);
// cerr << k - dis << ' ' << f [k - dis] + numNode << '\n';
for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
get (i. fi, x, dis + i. se, numNode + 1);
}
}
void update (ll x, ll par, ll dis, ll numNode) {
mini (f [dis], numNode);
//cerr << dis << ' ' << numNode << '\n';
vec. push_back (dis);
for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
update (i. fi, x, dis + i. se, numNode + 1);
}
}
void build (ll x) {
ll cnt = dfs (x, -1);
ll cen = finCen (x, -1, cnt);
vec. clear ();
del [cen] = 1;
for (pll i : adj [cen]) if (!del [i. fi]) {
get (i. fi, cen, i. se, 1);
update (i. fi, cen, i. se, 1);
}
// cerr << cen << '\n';
// for (int i = 0; i < 5; i ++) cerr << f [i] << ' ';
// cerr << '\n';
for (ll i : vec) f [i] = inf64;
for (pll i : adj [cen]) if (!del [i. fi]) build (i. fi);
}
ll best_path (int N, int K, int H [] [2], int L []) {
n = N; k = K;
// cerr << n << ' ' << k << '\n';
for (int i = 0, u, v, w; i < n - 1; i ++) {
u = H [i] [0];
v = H [i] [1];
w = L [i];
adj [u]. push_back ({v, w});
adj [v]. push_back ({u, w});
// cerr << u << ' ' << v << ' ' << w << '\n';
}
// for (int i = 0; i < n; i ++) {
// for (pll j : adj [i]) cerr << "(" << j. fi << ',' << j. se << "),";
// cerr << '\n';
// }
ans = inf64;
for (ll &i : f) i = inf64;
f [0] = 0;
build (0);
if (ans >= inf64) return -1;
return ans;
}
// int main () {
// ios::sync_with_stdio (0);
// cin. tie (0);
// cout. tie (0);
// #define task "untitled1"
// if (fopen (task".inp", "r")) {
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// }
// int N, K;
// cin >> N >> K;
// int H [N] [2];
// int L [N];
// 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];
// // cerr << N << ' ' << K << '\n';
// // for (int i = 0; i < N - 1; i ++) cerr << H [i] [0] << ' ' << H [i] [1] << '\n';
// // for (int i = 0; i < N - 1; i ++) cerr << L [i] << ' ';
// cout << best_path (N, K, H, L) << '\n';
// }
