#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n, k, ans = INT_MAX, proc[200005], si[200005];
vector<pair<int, int>> adj[200005];
map<int, int> occ[22][200005];
void dfs(int i, int p) {
si[i] = 1;
for (auto [j, _] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
dfs(j, i);
si[i] += si[j];
}
}
int centroid(int i, int p, int s) {
for (auto [j, w] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
if (si[j] > s/2) {
return centroid(j, i, s);
}
}
return i;
}
void calc(int i, int p, int d, int path, int l, int h, int c) {
if (path > k) {
return;
}
if (occ[l][h].find(path) == occ[l][h].end()) {
occ[l][h][path] = d;
} else {
occ[l][h][path] = min(occ[l][h][path], d);
}
if (k == path) {
ans = min(ans, d);
} else if (occ[l][c].find(k-path) != occ[l][c].end()) {
ans = min(ans, d+occ[l][c][k-path]);
}
for (auto [j, w] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
calc(j, i, d+1, path+w, l, h, c);
}
}
void decompose(int i, int l) {
dfs(i, -1);
if (si[i] == 1 || proc[i]) {
return;
}
i = centroid(i, -1, si[i]);
proc[i] = 1;
for (auto [j, w] : adj[i]) {
if (proc[j]) {
continue;
}
calc(j, i, 1, w, l, j, i);
if (occ[l][i].size() < occ[l][j].size()) {
occ[l][i].swap(occ[l][j]);
}
for (auto c : occ[l][j]) {
if (occ[l][i].find(c.first) != occ[l][i].end()) {
occ[l][i][c.first] = min(occ[l][i][c.first], c.second);
} else {
occ[l][i][c.first] = c.second;
}
}
}
for (auto [j, w] : adj[i]) {
if (proc[j]) {
continue;
}
decompose(j, l+1);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
decompose(0, 0);
if (ans == INT_MAX) {
return -1;
} else {
return ans;
}
}
