#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // cc_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>> adj[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;
++timerIdx;
int bestSize = 0, heavyChild = -1;
for (auto [v, w] : adj[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) adj[i].clear();
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});
}
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; // 非葉子
// -------- 改用 cc_hash_table --------
cc_hash_table<ll, int, chash> mp;
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]);
};
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]);
};
int x = leaf;
add(tin[x]); // 先加入葉子
while (parent[x] != -1) {
int p = parent[x];
// 處理父節點 p 的所有「輕兒」子樹
for (auto [child, _] : adj[p])
if (edgeCnt[tin[child]] > edgeCnt[tin[p]] && child != x) {
for (int i = tin[child]; i < tout[child]; ++i) relax(i, tin[p]);
for (int i = tin[child]; i < tout[child]; ++i) add(i);
}
// 處理父節點本身
relax(tin[p], tin[p]);
add(tin[p]);
x = p;
}
}
return ans == INF ? -1 : ans;
}
