#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 2e5;
ll n, k;
vector<pair<int, int>> adj[MAX];
int sz[MAX];
vector<bool> removed;
int get_size(int n, int p = -1) {
sz[n] = 1;
for (auto& [x, _] : adj[n]){
if (removed[x] || x == p) continue;
sz[n] += get_size(x, n);
}
return sz[n];
}
int find_centroid(int desired, int n, int p = -1) {
for (auto& [x, _] : adj[n]) {
if (removed[x] || x == p) continue;
if (sz[x] > desired) return find_centroid(desired, x, n);
}
return n;
}
int best = 1e9;
const int MAX_K = 1e6;
int m[MAX_K + 1];
vector<int> touched;
void solve(int n, int p, int d, ll l, bool filling) {
if (d > best || l > k) return;
if (filling) {
if (m[l] != -1) {
m[l] = min(m[l], d);
} else {
m[l] = d;
}
touched.push_back(l);
} else {
if (m[k - l] != -1) {
best = min(best, d + m[k - l]);
}
}
for (auto& [x, w] : adj[n]) {
if (removed[x] || x == p) continue;
solve(x, n, d + 1, l + w, filling);
}
}
void decompose(int n) {
int c = find_centroid(get_size(n) / 2, n);
removed[c] = true;
// if (touched.size() > 4000000) {
// cout << "hahaha";
// exit(-1);
// }
// int start = touched.size();
m[0] = 0;
for (auto& [x, w] : adj[c]) {
if (!removed[x]) {
solve(x, c, 1, w, false);
solve(x, c, 1, w, true);
}
}
for (int i = 0; i < touched.size(); ++i) {
m[touched[i]] = -1;
}
touched.clear();
for (auto& [x, _] : adj[c]) {
if (removed[x]) continue;
decompose(x);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
//touched.reserve(4000000);
memset(m, -1, sizeof(m));
n = N;
removed.assign(n, false);
k = K;
for (int i = 0; i < n - 1; ++i) {
int w = L[i];
int a = H[i][0], b = H[i][1];
adj[a].emplace_back(b, w);
adj[b].emplace_back(a, w);
}
decompose(0);
if (best == 1e9) {
return -1;
} else {
return best;
}
}
