#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9 + 1;
struct CentroidDecomposition {
vector<vector<array<int, 2>>>g;
vector<int>subSize;
vector<bool>removed;
vector<int>minDepth;
int k;
CentroidDecomposition(int n, int k, vector<vector<array<int, 2>>> &g) : k(k), g(g) {
subSize.resize(n);
removed.assign(n, false);
minDepth.assign(k + 1, oo);
}
int getSubSize(int v, int pa = -1) {
subSize[v] = 1;
for (auto [to, l] : g[v]) {
if (to != pa && !removed[to]) subSize[v] += getSubSize(to, v);
}
return subSize[v];
}
int findCentroid(int v, int halfSize, int pa = -1) {
for (auto [to, l] : g[v]) {
if (to != pa && !removed[to] && subSize[to] > halfSize) return findCentroid(to, halfSize, v);
}
return v;
}
void getDist(int v, int curLen, int depth, vector<array<int, 2>> &dist, int pa) {
if (curLen > k) return;
dist.push_back({curLen, depth});
for (auto [to, l] : g[v]) {
if (to != pa && !removed[to]) getDist(to, curLen + l, depth + 1, dist, v);
}
}
int shortestKlenPathThroughV(int v) {
vector<int>all;
int res = oo;
minDepth[0] = 0;
for (auto [to, l] : g[v]) {
if (!removed[to]) {
vector<array<int, 2>> dist;
getDist(to, l, 1, dist, v);
for (auto [len, depth] : dist) {
res = min(res, depth + minDepth[k - len]);
}
for (auto [len, depth] : dist) {
minDepth[len] = min(minDepth[len], depth);
all.push_back(len);
}
}
}
for (int len : all) {
minDepth[len] = oo;
}
return res;
}
int solve(int v = 0) {
int centroid = findCentroid(v, getSubSize(v) >> 1);
int res = oo;
removed[centroid] = true;
res = min(res, shortestKlenPathThroughV(centroid));
for (auto [to, l] : g[centroid]) {
if (!removed[to]) res = min(res, solve(to));
}
return res;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<array<int, 2>>>g(N);
for (int i = 0; i < N - 1; ++i) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
CentroidDecomposition cd(N, K, g);
int res = cd.solve();
if (res == oo) res = -1;
return res;
}
