// 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;
typedef pair<int, int> pii;
#define fi first
#define se second
void maxi (int &x, int y) {x = max (x, y);}
void mini (int &x, int y) {x = min (x, y);}
const ll maxN = 2e5 + 5, inf64 = 5e8, maxA = 1e6 + 5;
int N, K;
int H [maxN] [2];
int L [maxN];
int n, k, sz [maxN], f [maxA], ans;
bool del [maxN];
vector <int> vec;
vector <pii> adj [maxN];
int dfs (int x, int par) {
sz [x] = 1;
for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
sz [x] += dfs (i. fi, x);
}
return sz [x];
}
int finCen (int x, int par, int cnt) {
for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
if (sz [i. fi] >= cnt / 2) return finCen (i. fi, x, cnt);
}
return x;
}
void get (int x, int par, int dis, int numNode) {
if (k >= dis) mini (ans, f [k - dis] + numNode);
// cerr << k - dis << ' ' << f [k - dis] + numNode << '\n';
for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
get (i. fi, x, dis + i. se, numNode + 1);
}
}
void update (int x, int par, int dis, int numNode) {
if (dis <= k) {
mini (f [dis], numNode);
//cerr << dis << ' ' << numNode << '\n';
vec. push_back (dis);
}
for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
update (i. fi, x, dis + i. se, numNode + 1);
}
}
void build (int x) {
int cnt = dfs (x, -1);
int cen = finCen (x, -1, cnt);
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 (int i : vec) f [i] = inf64;
vec. clear ();
for (pii i : adj [cen]) if (!del [i. fi]) build (i. fi);
}
int 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];
// cerr << u << ' ' << v << ' ' << w << '\n';
adj [u]. push_back ({v, w});
adj [v]. push_back ({u, w});
}
// for (int i = 0; i < n; i ++) {
// for (pll j : adj [i]) cerr << "(" << j. fi << ',' << j. se << "),";
// cerr << '\n';
// }
ans = inf64;
for (int i = 1; i < maxA; 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);
// }
// cin >> N >> K;
// 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';
// }
