#include "race.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
template<typename T>
using vec = std::vector<T>;
using namespace std;
struct G {
int GENERATION = 0;
optional<int> ans;
int size, K;
vec<vec<array<int, 2>>> adj;
vec<bool> deleted;
vec<int> depth;
vec<int> uptow;
map<int, array<int, 2>> oracle;
G(int n, int k) : size(n), K(k), adj(n), deleted(n), depth(n), uptow(n), sub(n) {}
void undirectedAdd(int i, int j, int w) {
adj[i].push_back({j, w});
adj[j].push_back({i, w});
}
void initDFS(int u, int p = -1) {
if (uptow[u] == K)
ans = min(ans.value_or(INT32_MAX), depth[u]);
for (auto [c, w] : adj[u]) if (c != p && !deleted[c]) {
depth[c] = depth[u] + 1;
uptow[c] = uptow[u] + w;
initDFS(c, u);
}
}
void queryDFS(int u, int p) {
int tar = K - uptow[u];
if (oracle.find(tar) != oracle.end() && oracle[tar][1] == GENERATION) {
int partner = oracle[tar][0];
ans = min(ans.value_or(INT32_MAX), depth[u] + partner);
}
for (auto [c, _] : adj[u]) if (c != p && !deleted[c])
queryDFS(c, u);
}
void updateDFS(int u, int p) {
if (oracle.find(uptow[u]) == oracle.end() || oracle[uptow[u]][1] < GENERATION)
oracle[uptow[u]] = {INT32_MAX, GENERATION};
oracle[uptow[u]] = min(oracle[uptow[u]], {depth[u], GENERATION});
for (auto [c, _] : adj[u]) if (c != p && !deleted[c])
updateDFS(c, u);
}
void process(int r) {
depth[r] = uptow[r] = 0;
initDFS(r);
for (auto [c, _] : adj[r]) if (!deleted[c]) {
queryDFS(c, r);
updateDFS(c, r);
}
}
int cn;
vec<int> sub;
void dfs0(int u, int p = -1) {
cn++;
sub[u] = 1;
for (auto [c, _] : adj[u]) if (c != p && !deleted[c]) {
dfs0(c, u);
sub[u] += sub[c];
}
}
int dfs1(int u, int p = -1) {
for (auto [c, _] : adj[u]) if (c != p && !deleted[c] && sub[c] > cn / 2) {
return dfs1(c, u);
}
return u;
}
void decompose(int r = 0) {
cn = 0;
dfs0(r);
int cen = dfs1(r);
GENERATION++;
process(cen);
deleted[cen] = true;
for (auto [c, _] : adj[cen]) if (!deleted[c])
decompose(c);
}
};
int best_path(int N, int K, int H[][2], int L[]) {
G g(N, K);
for (int i = 0; i < N - 1; i++)
g.undirectedAdd(H[i][0], H[i][1], L[i]);
g.decompose();
return g.ans.value_or(-1);
}
