#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, k, ans = INF;
vector< map<int, int> > g;
vector<int> sz;
map<int, int> len, new_len;
int dfs(int u, int par) {
sz[u] = 1;
for (auto& v : g[u]) {
if (v.first != par) {
sz[u] += dfs(v.first, u);
}
}
return sz[u];
}
int find_centroid(int u, int par, int n) {
for (auto& v : g[u]) {
if (v.first != par && sz[v.first] > n / 2) {
return find_centroid(v.first, u, n);
}
}
return u;
}
void find_path(int u, int par, int cur_dist, int cur_len) {
if (cur_dist > k) {
return;
}
if (len.count(k - cur_dist)) {
ans = min(ans, len[k - cur_dist] + cur_len);
}
if (!new_len.count(cur_dist)) {
new_len[cur_dist] = cur_len;
} else {
new_len[cur_dist] = min(new_len[cur_dist], cur_len);
}
for (auto& v : g[u]) {
if (v.first != par) {
find_path(v.first, u, cur_dist + v.second, cur_len + 1);
}
}
}
void find_path(int u, int par) {
len.clear();
new_len.clear();
len[0] = 0;
for (auto& v : g[u]) {
if (v.first != par) {
find_path(v.first, u, v.second, 1);
for (auto& p : new_len) {
if (!len.count(p.first)) {
len[p.first] = p.second;
} else {
len[p.first] = min(len[p.first], p.second);
}
}
new_len.clear();
}
}
}
void decompose(int u, int par) {
int n = dfs(u, par);
int centroid = find_centroid(u, par, n);
find_path(centroid, par);
vector<int> tmp;
for (auto& v : g[centroid]) {
tmp.push_back(v.first);
}
for (auto& v : tmp) {
if (v != par) {
g[centroid].erase(v);
g[v].erase(centroid);
decompose(v, centroid);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
g.resize(n);
sz.resize(n);
for (int i = 0; i < n - 1; i++) {
g[H[i][0]].insert({H[i][1], L[i]});
g[H[i][1]].insert({H[i][0], L[i]});
}
decompose(0, -1);
if (ans == INF) {
return -1;
}
return ans;
}
