#include "race.h"
#include <vector>
#include <unordered_map>
#include <cassert>
#include <climits>
const int MAXN = 2e5;
using Map = std::unordered_map<long long, int>; // map from sum to smallest dist
struct Edge {
int node;
int weight;
};
int n, k;
std::vector<Edge> a[MAXN];
long long sum[MAXN]; // weight sum from root to i
int dist[MAXN]; // edges between root and i
int best_k_path = INT_MAX;
void build_adj(int h[][2], int l[]) {
for (int i = 0; i < n - 1; i++) {
a[h[i][0]].push_back({ h[i][1], l[i] });
a[h[i][1]].push_back({ h[i][0], l[i] });
}
}
void precalc_dfs(int node, int parent) {
for (auto [child, weight] : a[node]) {
if (child == parent) continue;
sum[child] = sum[node] + weight;
dist[child] = dist[node] + 1;
precalc_dfs(child, node);
}
}
// returns smallest dist of sum k
int find_smallest_k_path(const Map& dst, const Map& src, int node) {
assert(dst.size() >= src.size());
int res = INT_MAX;
for (auto [s, d] : src) {
if (dst.count(k - s + 2 * sum[node])) {
res = std::min(res, dst.at(k - s + 2 * sum[node]) + d - 2 * dist[node]);
}
}
return res;
}
void merge_into(Map& dst, const Map& src) {
assert(dst.size() >= src.size());
for (auto [s, d] : src) {
if (dst.count(s)) {
dst[s] = std::min(dst[s], d);
} else {
dst[s] = d;
}
}
}
Map dfs(int node, int parent) {
Map res;
res[sum[node]] = dist[node];
for (auto [child, _] : a[node]) {
if (child == parent) continue;
Map m = dfs(child, node);
if (m.size() > res.size()) {
std::swap(res, m);
}
best_k_path = std::min(best_k_path, find_smallest_k_path(res, m, node));
merge_into(res, m);
}
return res;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
build_adj(H, L);
precalc_dfs(0, -1);
dfs(0, -1);
return best_k_path != INT_MAX ? best_k_path : -1;
}
