#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using LL = long long;
const int N = 2E5 + 69;
vector < pair <int, int> > G[N];
int k, mx_depth, sz[N], pa[N], processed[N], l[N];
map <int, int> mp;
int ans = INT_MAX;
int dfs (int u, int p) {
sz[u] = 1;
for(auto [v, idx] : G[u]) if (v != p and !processed[v]) {
sz[u] += dfs(v, u);
}
return sz[u];
}
int centroid (int u, int p, int n) {
for(auto [v, idx] : G[u]) if(v != p and !processed[v]) {
if (sz[v] > n / 2) return centroid (v, u, n);
}
return u;
}
void get_cnt (int u, int p, bool filling, int len, int depth = 1) {
// cerr << ((filling) ? "FILLING " : "QUERY ") << u << ' ' << p << ' ' << len << ' ' << depth << '\n';
if (len > k) return;
// mx_depth = max (mx_depth, depth);
if (filling) {
if (mp.count (len)) mp[len] = min (mp[len], depth);
else mp[len] = depth;
// cerr << "UPDATED: " << len << ' ' << mp[len] << endl;
}
else {
// cerr << "QUERYING " << k - len << '\n';
if (mp.count (k - len)) ans = min (ans, mp[k - len] + depth);
}
for (auto [next, idx] : G[u]) if (next != p and !processed[next]) {
get_cnt (next, u, filling, len + l[idx], depth + 1);
}
}
void build (int u = 0, int p = -1) {
int n = dfs (u, p);
int c = centroid (u, p, n);
processed[c] = 1;
// cerr << c << endl;
// mx_depth = 0;
for (auto [next, idx] : G[c]) if (next != p and !processed[next]) {
get_cnt (next, c, false, l[idx]);
// for (auto [l, r] : mp) cerr << l << ' ' << r << endl;
get_cnt (next, c, true, l[idx]);
}
if (mp.count (k)) ans = min (ans, mp[k]);
mp.clear ();
for (auto [next, idx] : G[c]) {
if (!processed[next]) build (next, c);
}
}
int best_path (int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N; i++) l[i] = L[i];
for (int i = 0; i < N - 1; i++) {
G[H[i][0]].push_back ({H[i][1], i});
G[H[i][1]].push_back ({H[i][0], i});
}
build ();
if (ans == INT_MAX) ans = -1;
return ans;
}
// int main() {
// cin.tie(nullptr) -> ios_base::sync_with_stdio(false);
// int n, kk;
// cin >> n >> kk;
// int H[n][2], L[n];
// for (int i = 0; i < n - 1; i++) cin >> H[i][0] >> H[i][1];
// for (int i = 0; i < n; i++) cin >> L[i];
// cout << best_path (n, kk, H, L) << '\n';
// return 0;
// }
