#include <algorithm>
#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp> // gp_hash_table
#define SZ(x) static_cast<int>((x).size())
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
const int INF = 1e9;
const int MAXN = 200'001;
/* -------- 自訂雜湊 (split-mix64) -------- */
struct chash {
size_t operator()(ll x) const {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return static_cast<size_t>(x ^ (x >> 31));
}
};
/* -------- 全域陣列 -------- */
vector<pair<int,int>> e[MAXN];
int parent [MAXN];
int tin [MAXN], tout[MAXN], timerIdx;
ll depth [MAXN];
int edgeCnt [MAXN];
/* -------- DFS：flatten + 找重兒 -------- */
void dfs(int u, int p)
{
tin[u] = timerIdx++;
int bestSize = 0, heavyChild = -1;
for (auto [v,w] : e[u]) if (v != p) {
depth[timerIdx] = depth[tin[u]] + w;
edgeCnt[timerIdx] = edgeCnt[tin[u]] + 1;
dfs(v, u);
int sub = tout[v] - tin[v];
if (sub > bestSize) { bestSize = sub; heavyChild = v; }
}
if (heavyChild != -1) parent[heavyChild] = u;
tout[u] = timerIdx;
}
/* -------- 主解 -------- */
int best_path(int N, int K, int H[][2], int L[])
{
/* 建樹 */
for (int i = 0; i < N; ++i) e[i].clear();
for (int i = 0; i < N - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
e[u].push_back({v,w});
e[v].push_back({u,w});
}
fill(parent, parent+N, -1);
timerIdx = 0;
dfs(0, -1);
int ans = INF;
for (int leaf = 0; leaf < N; ++leaf) {
if (tin[leaf] + 1 < tout[leaf]) continue; // 非葉子
int x = leaf;
gp_hash_table<ll,int,chash> mp; // ← 改用 gp_hash_table
auto relax = [&](int idx, int lcaIdx) {
ll need = K + 2*depth[lcaIdx] - depth[idx];
auto it = mp.find(need);
if (it != mp.end())
ans = min(ans,
edgeCnt[idx] + it->second - 2*edgeCnt[lcaIdx]);
};
auto add = [&](int idx) {
ll d = depth[idx];
auto it = mp.find(d);
if (it == mp.end()) mp[d] = edgeCnt[idx];
else it->second = min(it->second, edgeCnt[idx]);
};
add(tin[x]);
while (parent[x] != -1) {
int p = parent[x];
for (auto [y,_] : e[p]) {
if (edgeCnt[tin[y]] < edgeCnt[tin[p]] || y == x) continue;
for (int i = tin[y]; i < tout[y]; ++i) relax(i, tin[p]);
for (int i = tin[y]; i < tout[y]; ++i) add(i);
}
relax(tin[p], tin[p]);
add (tin[p]);
x = p;
}
}
return ans == INF ? -1 : ans;
}
