#include<bits/stdc++.h>
using namespace std;
const int V = 3e5;
int H[V][2];
int L[V];
int best_path(int N, int K, int H[][2], int L[]) {
const int INF = 1e9;
int ans = INF;
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i+1 < N; ++i) {
// cout << H[i][0] << ' ' << H[i][1] << endl;
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
vector<bool> deleted(N);
vector<pair<int, int>> max_sub(N);
auto dfs = [&](auto&& self, int cur, int prv) -> int {
int sz = 1;
max_sub[cur] = {0, -1};
for (auto [nxt, weight] : adj[cur]) {
if (nxt == prv || deleted[nxt]) continue;
int cur_sz = self(self, nxt, cur);
sz += cur_sz;
max_sub[cur] = max(max_sub[cur], {cur_sz, nxt});
}
return sz;
};
auto get_dist = [&](auto& self, int cur, int prv, int64_t depth, int level, auto& path) -> void {
if (depth > K)
path.push_back({depth, level});
for (auto [nxt, weight] : adj[cur]) {
if (nxt == prv || deleted[nxt]) continue;
self(self, nxt, cur, depth + weight, level + 1, path);
}
};
auto rec = [&](auto&& self, int cur) -> void {
int total_sz = dfs(dfs, cur, -1);
while (max_sub[cur].first * 2 > total_sz) cur = max_sub[cur].second;
deleted[cur] = true;
vector<int> vals(K + 1, INF);
for (auto [nxt, weight] : adj[cur]) {
if (deleted[nxt]) continue;
vector<pair<int, int>> path; path.reserve(total_sz);
get_dist(get_dist, nxt, -1, weight, 1, path);
for (auto [dist, level] : path) {
if (dist > K) continue;
ans = min(ans, vals[K - dist] + level);
if (vals[K - dist] == INF && dist == K) {
ans = min(ans, level);
}
}
for (auto [dist, level] : path) {
if (dist > K) continue;
vals[dist] = min(vals[dist], level);
}
}
for (auto [nxt, weight] : adj[cur]) {
if (deleted[nxt]) continue;
self(self, nxt);
}
};
rec(rec, 0);
return (ans == INF ? -1 : ans);
}
]