#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using li = long long;
using ld = long double;
using pi = pair<int, int>;
using pli = pair<li, li>;
#define all(c) c.begin(), c.end()
#define prec(n) setprecision(n) << fixed
template <typename K, typename V>
class map_m : public map<K, V> {
public:
auto emplace_minimal(K k, V v) {
auto [it, success] = this->try_emplace(k, v);
if (!success && it->second > v) it->second = v;
return it;
}
};
class Tree {
public:
int V, R;
vector<vector<pair<int, li>>> adj, tr;
vector<int> sz, pr, ofl;
vector<map_m<li, int>> mp;
vector<li> ofw;
explicit Tree(int _V)
: V(_V), adj(V), tr(V), sz(V), pr(V), ofl(V), mp(V), ofw(V) {
iota(all(pr), 0);
}
void emplace_edge(int u, int v, li w) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
void compile(int _R) {
R = _R;
function<void(int, optional<int>)> dfs = [&](int h, optional<int> p) {
sz[h] = 1;
for (auto [t, W] : adj[h]) {
if (p && t == *p) continue;
dfs(t, h);
tr[h].emplace_back(t, W);
if (sz[t] > sz[tr[h][0].first]) swap(tr[h][0], tr[h].back());
sz[h] += sz[t];
}
if (!tr[h].empty()) pr[h] = pr[tr[h][0].first];
adj[h].clear();
adj[h].shrink_to_fit();
};
dfs(R, nullopt);
}
optional<int> solve(int h, li K) {
optional<int> ret;
multiset<pair<li, int>> courses;
for (auto [t, W] : tr[h]) {
auto sol = solve(t, K);
if (sol) {
if (!ret)
ret = sol;
else
ret = min(*ret, *sol);
}
auto it = mp[pr[t]].find(K - W - ofw[pr[t]]);
if (it != mp[pr[t]].end()) {
if (!ret)
ret = ofl[pr[t]] + 1 + it->second;
else
ret = min(*ret, ofl[pr[t]] + 1 + it->second);
}
}
for (auto [t, W] : tr[h]) {
if (pr[h] != pr[t]) {
auto it = mp[pr[t]].begin();
while (it != mp[pr[t]].end()) {
if (ret && it->second + ofl[pr[t]] + 1 > *ret) {
it = mp[pr[t]].erase(it);
continue;
}
++it;
}
for (auto [w, l] : mp[pr[t]])
courses.emplace(W + w + ofw[pr[t]], l + ofl[pr[t]] + 1);
}
}
for (auto [t, W] : tr[h]) {
if (pr[h] != pr[t]) {
for (auto [w, l] : mp[pr[t]])
courses.erase({W + w + ofw[pr[t]], l + ofl[pr[t]] + 1});
for (auto [w, l] : mp[pr[t]]) {
auto remain = K - W - w - ofw[pr[t]];
if (remain < 0) break;
auto it = courses.lower_bound({remain, -1});
if (it != courses.end() && it->first == remain) {
if (!ret)
ret = l + ofl[pr[t]] + 1 + it->second;
else
ret = min(*ret, l + ofl[pr[t]] + 1 + it->second);
}
}
for (auto [w, l] : mp[pr[t]])
courses.emplace(W + w + ofw[pr[t]], l + ofl[pr[t]] + 1);
}
}
if (h != pr[h]) {
auto [t, W] = tr[h][0];
for (auto [w, l] : courses) {
auto remain = K - W - w - ofw[pr[t]];
auto it = mp[pr[t]].find(remain);
if (it != mp[pr[t]].end()) {
if (!ret)
ret = l + ofl[pr[t]] + 1 + it->second;
else
ret = min(*ret, l + ofl[pr[t]] + 1 + it->second);
}
}
ofw[pr[h]] += tr[h][0].second;
ofl[pr[h]]++;
}
for (auto [t, W] : adj[h]) mp[pr[t]].clear();
for (auto [w, l] : courses)
mp[pr[h]].emplace_minimal(w - ofw[pr[h]], l - ofl[pr[h]]);
mp[pr[h]].emplace_minimal(-ofw[pr[h]], -ofl[pr[h]]);
auto it = mp[pr[h]].upper_bound(K - ofw[pr[h]]);
mp[pr[h]].erase(it, mp[pr[h]].end());
return ret;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
Tree T(N);
for (int i = 0; i < N - 1; i++) {
T.emplace_edge(H[i][0], H[i][1], L[i]);
}
T.compile(0);
auto res = T.solve(0, K);
return res ? *res : -1;
}
