#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define ii pair<int, int>
#define ll long long
int N, K, ans, cnt[1000100], subSize[MAXN], root[MAXN];
vector<ii> adj[MAXN];
inline void minimize(int& a, int b) {
if (a == -1 || a > b) {
a = b;
}
}
void get_cnt(int sum, bool filling, int cur, int par = -1, int depth = 1) {
if (sum > K) {
return;
}
if (filling) {
minimize(cnt[sum], depth);
}
else {
if (cnt[K - sum] != -1) {
minimize(ans, depth + cnt[K - sum]);
}
}
for (auto& oPair : adj[cur]) {
int next = oPair.first;
int cost = oPair.second;
if (next != par && !root[next]) {
get_cnt(sum + cost, filling, next, cur, depth + 1);
}
}
}
void del(int sum, int cur, int par = -1) {
if (sum > K) return;
cnt[sum] = -1;
for (auto& oPair : adj[cur]) {
int next = oPair.first;
int cost = oPair.second;
if (next != par && !root[next]) {
del(sum + cost, next, cur);
}
}
}
// Find subtree size under each node.
int dfs(int cur, int par = -1) {
subSize[cur] = 1;
for (auto& oPair : adj[cur]) {
int next = oPair.first;
int cost = oPair.second;
if (next != par && !root[next]) {
subSize[cur] += dfs(next, cur);
}
}
return subSize[cur];
}
// Get the centroid within the subtree.
int get_centroid(int size, int cur, int par = -1) {
for (auto& oPair : adj[cur]) {
int next = oPair.first;
if (next != par && !root[next] && 2 * subSize[next] > size) {
return get_centroid(size, next, cur);
}
}
return cur;
}
void centroid(int cur = 0) {
cur = get_centroid(dfs(cur), cur);
root[cur] = 1;
cnt[0] = 0;
for (auto& oPair : adj[cur]) {
int next = oPair.first;
int cost = oPair.second;
if (!root[next]) {
get_cnt(cost, false, next);
get_cnt(cost, true, next);
}
}
for (auto& oPair : adj[cur]) {
int next = oPair.first;
int cost = oPair.second;
if (!root[next]) {
del(cost, next);
}
}
for (auto& oPair : adj[cur]) {
int next = oPair.first;
if (!root[next]) {
centroid(next);
}
}
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n;
K = k;
for (int i = 0, u, v; i < N - 1; i++) {
u = H[i][0];
v = H[i][1];
adj[u].push_back(ii(v, L[i]));
adj[v].push_back(ii(u, L[i]));
}
ans = -1;
memset(cnt, -1, sizeof(cnt));
centroid();
return ans;
}
