#include <bits/stdc++.h>
#define SZ(x) static_cast<int>((x).size())
using namespace std;
using ll = long long;
int best_path(int N, int K, int H[][2], int L[]) {
/* ---------- 1. 建樹 ---------- */
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
/* ---------- 2. flatten + 重兒標記 ---------- */
vector<int> tin(N), tout(N), heavyPar(N, -1), flatSteps(N);
vector<ll> flatDepth(N);
int timer = 0;
auto dfs = [&](auto &&self, int u, int p, ll dSum, int dCnt) -> void {
// 進入節點 u
tin[u] = timer;
flatDepth[timer] = dSum;
flatSteps[timer] = dCnt;
++timer;
// 找最大子樹 (= 重兒)
int bestSize = 0, heavyChild = -1;
for (auto [v, w] : adj[u])
if (v != p) {
int before = timer;
self(self, v, u, dSum + w, dCnt + 1);
int sub = timer - before;
if (sub > bestSize) {
bestSize = sub;
heavyChild = v;
}
}
if (heavyChild != -1) heavyPar[heavyChild] = u;
tout[u] = timer; // 子樹區間 [tin, tout)
};
dfs(dfs, 0, -1, 0LL, 0);
/* ---------- 3. heavy-light + 小併大 ---------- */
const int INF = 1e9;
int answer = INF;
for (int leaf = 0; leaf < N; ++leaf) {
if (tin[leaf] + 1 < tout[leaf]) continue; // 非葉子
unordered_map<ll, int> best; // 距離 → 最少邊數
auto add = [&](int idx) {
ll d = flatDepth[idx];
int s = flatSteps[idx];
if (!best.count(d)) best[d] = s;
else best[d] = min(best[d], s);
};
auto relax = [&](int idx, int lcaIdx) {
ll need = K + 2 * flatDepth[lcaIdx] - flatDepth[idx];
if (best.count(need))
answer = min(answer,
flatSteps[idx] + best[need] - 2 * flatSteps[lcaIdx]);
};
add(tin[leaf]); // 把葉子本身先加入
for (int u = leaf; heavyPar[u] != -1; u = heavyPar[u]) {
int p = heavyPar[u];
// 處理父節點 p 的所有「輕兒」子樹
for (auto [child, _] : adj[p])
if (flatSteps[tin[child]] > flatSteps[[tin[p]] && child != u) {
for (int idx = tin[child]; idx < tout[child]; ++idx)
relax(idx, tin[p]);
for (int idx = tin[child]; idx < tout[child]; ++idx)
add(idx);
}
// 處理父節點本身
relax(tin[p], tin[p]);
add(tin[p]);
}
}
return (answer == INF ? -1 : answer);
}
