//centroid decomposition
//Submission : https://dmoj.ca/submission/5575237
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
int n, k, ans = 1e9;
vector<pll> adj[maxn];
int L[maxn], vis[maxn], siz[maxn], H[maxn][2];
map<int, int> all, tmp;
// find centroid, calculate answer for centroid, remove the node and recurse for further centroids
void dfssz(int pos, int prev){
siz[pos] = 1;
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfssz(x, pos);
siz[pos] += siz[x];
}
}
void dfsans(int pos, int prev, int dis, int cnt){
if(dis > k) return;
if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
else tmp[dis] = cnt;
if(all.find(k - dis) != all.end()) ans = min(ans, cnt + all[k - dis]);
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfsans(x, pos, dis + L[idx], cnt + 1);
}
}
int get_centroid(int pos, int prev, int sz){
for(auto [x, idx] : adj[pos]){
if(x != prev && !vis[x] && siz[x] > sz / 2) return get_centroid(x, pos, sz);
}
return pos;
}
void centroid_decomposition(int pos){
dfssz(pos, -1);
int centroid = get_centroid(pos, -1, siz[pos]);
vis[centroid] = 1;
all.clear();
all[0] = 0;
for(auto [x, idx] : adj[centroid]){
tmp.clear();
if(vis[x]) continue;
dfsans(x, -1, L[idx], 1);
for(auto [dis, cnt] : tmp){
if(all.find(k - dis) != all.end()) {
ans = min(ans, cnt + all[k - dis]);
}
}
for(auto [dis, cnt] : tmp){
if(all.find(dis) != all.end()) all[dis] = min(all[dis], cnt);
else all[dis] = cnt;
}
}
for(auto [x, idx] : adj[centroid]){
if(vis[x]) continue;
centroid_decomposition(x);
}
}
int best_path(int N, int K, int H[][2], int l[]){
n = N, k = K;
for(int i = 0; i < n - 1; i++){
adj[H[i][0]].eb(H[i][1], i);
adj[H[i][1]].eb(H[i][0], i);
}
for(int i = 0; i < n - 1; i++) L[i] = l[i];
centroid_decomposition(0);
return (ans < 1e9 ? ans : -1);
}
