#include <bits/stdc++.h>
using namespace std;
int best_path(int n, int k, int h[][2], int l[]) {
int ans = INT_MAX;
vector<vector<pair<int, int>>> G(n + 1);
vector<int> seen(n + 1), s(n + 1);
map<int, int> m;
for (int i = 0; i < n - 1; ++i) {
G[1 + h[i][0]].emplace_back(1 + h[i][1], l[i]);
G[1 + h[i][1]].emplace_back(1 + h[i][0], l[i]);
}
function<void(int, int)> dfs = [&](int node, int last) {
s[node] = 1;
for (auto x : G[node])
if (x.first != last && !seen[x.first]) {
dfs(x.first, node);
s[node] += s[x.first];
}
};
function<int(int, int, int)> centroid = [&](int node, int last, int n) {
for (auto x : G[node])
if (x.first != last && !seen[x.first] && s[x.first] > n / 2)
return centroid(x.first, node, n);
return node;
};
function<void(int, int, int, int, int)> dfs2 = [&](int node, int last, int length1, int length2, int mode) {
if (mode) {
if (m.count(k - length1))
ans = min(ans, m[k - length1] + length2);
}
else {
if (m.count(length1))
m[length1] = min(m[length1], length2);
else
m[length1] = length2;
}
for (auto x : G[node])
if (x.first != last && !seen[x.first])
dfs2(x.first, node, length1 + x.second, length2 + 1, mode);
};
function<void(int)> Build = [&](int node) {
dfs(node, 0);
int c = centroid(node, 0, s[node]);
seen[c] = 1;
m.clear();
m[0] = 0;
for (auto x : G[c])
if (!seen[x.first])
dfs2(x.first, c, x.second, 1, 1), dfs2(x.first, c, x.second, 1, 0);
for (auto x : G[c])
if (!seen[x.first])
Build(x.first);
};
Build(1);
return ans != INT_MAX ? ans : -1;
};
