#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int, 2>>> adj;
int n, k, ans = 2e9, nodes;
vector<int> sub;
bitset<200000> is_cent;
map<int, int> mp2;
void precalc (int u, int p = -1) {
sub[u] = 1;
++nodes;
for (auto &v : adj[u]) {
if (!is_cent[v[0]] && v[0] ^ p) {
precalc(v[0], u);
sub[u] += sub[v[0]];
}
}
}
int centroid (int u, int p = -1) {
for (auto &v : adj[u]) {
if (!is_cent[v[0]] && v[0] ^ p) {
if (sub[v[0]] > nodes / 2) {
return centroid(v[0], u);
}
}
}
return u;
}
void update (map<int, int> &m, int k, int v) {
if (m.count(k)) {
m[k] = min(m[k], v);
}
else {
m[k] = v;
}
}
void dfs (int u, int p, int sum, int d) {
if (sum > k) {
return;
}
update(mp2, sum, d);
for (auto &v : adj[u]) {
if (!is_cent[v[0]] && v[0] ^ p) {
dfs(v[0], u, sum + v[1], d + 1);
}
}
}
void decompose (int u = 0) {
nodes = 0;
precalc(u);
int cent = centroid(u);
map<int, int> mp;
mp[0] = 0;
is_cent[cent] = 1;
for (auto &v : adj[cent]) {
if (is_cent[v[0]]) {
continue;
}
mp2.clear();
dfs(v[0], cent, v[1], 1);
for (auto &p : mp2) {
if (mp.count(k - p.first)) {
ans = min(ans, p.second + mp[k - p.first]);
}
}
for (auto &p : mp2) {
update(mp, p.first, p.second);
}
}
for (auto &v : adj[cent]) {
if (!is_cent[v[0]]) {
decompose(v[0]);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
adj.resize(n);
sub.resize(n);
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();
return ans == 2e9 ? -1 : ans;
}
