#include <bits/stdc++.h>
using namespace std;
int best_path(int n, int k, int h[][2], int l[])
{
const int maxn = 200001;
const int inf = 0x3f3f3f3f;
vector<pair<int, int>> graph[maxn];
for (int i = 0; i < n - 1; i++)
{
int u = h[i][0];
int v = h[i][1];
int w = l[i];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
int size[maxn];
bool ignored[maxn];
memset(ignored, 0, sizeof(ignored));
auto get_centroid = [&](int root) {
{
auto dfs = [&](auto dfs, int vertex, int parent) -> void {
size[vertex] = 0;
for (auto [adjacent, _]: graph[vertex])
if (adjacent != parent) if (!ignored[adjacent])
{
dfs(dfs, adjacent, vertex);
size[vertex] += size[adjacent];
}
size[vertex]++;
};
dfs(dfs, root, -1);
}
auto dfs = [&](auto dfs, int vertex, int parent) -> int {
for (auto [adjacent, _]: graph[vertex])
if (adjacent != parent) if (!ignored[adjacent])
if (size[adjacent] > size[root] / 2)
return dfs(dfs, adjacent, vertex);
return vertex;
};
return dfs(dfs, root, -1);
};
const int maxk = 1000001;
int depth[maxk];
int counters[maxk];
memset(counters, 0, sizeof(counters));
int counter = 0;
auto get = [&](int index) {
if (index >= maxk) return inf;
if (counters[index] == counter) return depth[index];
return inf;
};
auto store = [&](int index, int value) {
if (index >= maxk) return;
counters[index] = counter;
depth[index] = value;
};
auto clear = [&]() {
counter++;
};
int result = inf;
struct distance_t
{
int depth, distance;
};
distance_t distances[maxn];
auto dfs = [&](auto dfs, int vertex) -> void {
int centroid = get_centroid(vertex);
ignored[centroid] = true;
clear();
store(0, 0);
for (auto [adjacent, initial_edge]: graph[centroid])
{
if (ignored[adjacent]) continue;
int counter = 0;
auto dfs = [&](auto dfs, int vertex, int parent, int depth, int distance) -> void {
auto clamp = [&](int x) {
return min(inf, x);
};
distances[counter++] = { depth + 1, clamp(distance + initial_edge) };
for (auto [adjacent, weight]: graph[vertex])
if (adjacent != parent) if (!ignored[adjacent])
dfs(dfs, adjacent, vertex, depth + 1, clamp(distance + weight));
};
dfs(dfs, adjacent, centroid, 0, 0);
for (int i = 0; i < counter; i++)
{
auto &distance = distances[i];
int companion = k - distance.distance;
if (companion < 0) continue;
result = min(result, get(companion) + distance.depth);
}
for (int i = 0; i < counter; i++)
{
auto &distance = distances[i];
store(distance.distance, min(get(distance.distance), distance.depth));
}
}
for (auto [adjacent, _]: graph[centroid])
if (!ignored[adjacent])
dfs(dfs, adjacent);
};
dfs(dfs, 0);
return result == inf ? -1 : result;
}
