#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
const ll INF = 0x1fffffffffffffff;
bool chmin(ll& a, ll b){ if(a > b){ a = b; return 1; } return 0; }
bool chmax(ll& a, ll b){ if(a < b){ a = b; return 1; } return 0; }
ll k;
ll solve(vector<vector<pair<ll, ll>>> g){
if(g.size() == 1) return INF;
const ll n = g.size();
vector<ll> siz(n, 1);
ll max = 0, a, b, d;
auto dfs_size = [&](ll from, ll at, ll dist, auto dfs) -> void {
for(auto [i, d] : g[at]) if(i != from){
dfs(at, i, d, dfs);
siz[at] += siz[i];
}
if(siz[at] * 2 <= n && chmax(max, siz[at])){
a = from; b = at; d = dist;
}
};
dfs_size(-1, 0, 0, dfs_size);
unordered_map<ll, ll> lower;
vector<vector<pair<ll, ll>>> g_lower(1), g_upper(1);
auto dfs_lower = [&](ll from, ll at, ll depth, ll dist, auto dfs) -> void {
if(!lower.try_emplace(dist, depth).second) chmax(lower[dist], depth);
const ll at2 = g_lower.size() - 1;
for(auto [i, d] : g[at]) if(i != from){
g_lower[at2].emplace_back(g_lower.size(), d);
g_lower.push_back({{at2, d}});
dfs(at, i, depth - 1, dist - d, dfs);
}
};
dfs_lower(a, b, -1, -d, dfs_lower);
ll ans = INF;
auto dfs_upper = [&](ll from, ll at, ll depth, ll dist, auto dfs) -> void {
if(lower.count(dist - k)) chmin(ans, depth - lower[dist - k]);
const ll at2 = g_upper.size() - 1;
for(auto [i, d] : g[at]) if(i != from){
g_upper[at2].emplace_back(g_upper.size(), d);
g_upper.push_back({{at2, d}});
dfs(at, i, depth + 1, dist + d, dfs);
}
};
dfs_upper(b, a, 0, 0, dfs_upper);
chmin(ans, solve(g_lower));
chmin(ans, solve(g_upper));
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
vector<vector<pair<ll, ll>>> g(N);
for(ll i = 0; i < N - 1; i++){
const auto [a, b] = H[i];
const int c = L[i];
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
return solve(g);
}
