#include "race.h"
#include <cassert>
#include <cstdint>
#include <functional>
#include <unordered_map>
#include <vector>
using namespace std;
using i6 = int64_t;
struct Edge {
int len;
int dst;
};
vector<vector<Edge>> g;
int res = INT32_MAX;
int n;
int k;
vector<uint8_t> used;
struct CustomHash {
// Seed with a fixed random value for consistency
static uint64_t fixedRandom;
size_t operator()(uint64_t x) const {
// Use splitmix64 hash function
x += fixedRandom;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
};
uint64_t CustomHash::fixedRandom = 1337;
int find_centroid(int root, int total_size) {
vector<int> sizes(n);
function<int(int, int)> find_sizes = [&](int p, int u) -> int {
for (auto e : g[u]) {
if (e.dst == p || used[e.dst])
continue;
sizes[u] += find_sizes(u, e.dst);
}
return sizes[u];
};
find_sizes(-1, root);
function<int(int, int)> find_centroid_impl = [&](int p, int u) {
for (auto e : g[u]) {
if (e.dst == p || used[e.dst])
continue;
if (sizes[e.dst] > total_size / 2) {
return find_centroid_impl(u, e.dst);
}
}
return u;
};
return find_centroid_impl(-1, root);
}
void compute_solution(int root, int total_size) {
if (used[root])
return;
int centroid = find_centroid(root, total_size);
used[centroid] = 1;
unordered_map<int, int> comp_sizes;
{
unordered_map<i6, int, CustomHash> min_depth_by_dist;
unordered_map<i6, int, CustomHash> new_min_depth_by_dist;
int comp_size = 0;
function<void(int, int, int, i6)> walk = [&](int parent, int u, int depth, i6 dist) {
comp_size++;
if (dist > k || depth >= res)
return;
auto it = new_min_depth_by_dist.find(dist);
if (it == new_min_depth_by_dist.end() || depth < it->second) {
new_min_depth_by_dist[dist] = depth;
}
for (auto& e : g[u]) {
if (e.dst == parent || used[e.dst])
continue;
walk(u, e.dst, depth + 1, dist + e.len);
}
};
for (auto& e : g[centroid]) {
if (used[e.dst])
continue;
comp_size = 0;
new_min_depth_by_dist.clear();
walk(centroid, e.dst, 1, e.len);
comp_sizes[e.dst] = comp_size;
for (auto& [dist, depth] : new_min_depth_by_dist) {
if (depth >= res)
continue;
i6 rem_dist = k - dist;
if (rem_dist == 0) {
res = min(res, depth);
} else if (rem_dist > 0) {
auto it = min_depth_by_dist.find(rem_dist);
if (it != min_depth_by_dist.end()) {
res = min(res, depth + it->second);
}
}
}
for (auto& [dist, depth] : new_min_depth_by_dist) {
auto it = min_depth_by_dist.find(dist);
if (it == min_depth_by_dist.end() || depth < it->second) {
min_depth_by_dist[dist] = depth;
}
}
}
}
for (auto& e : g[centroid]) {
compute_solution(e.dst, comp_sizes[e.dst]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
used.resize(N);
g.resize(n);
for (int i = 0; i < N; i++) {
g[H[i][0]].push_back({L[i], H[i][1]});
g[H[i][1]].push_back({L[i], H[i][0]});
}
compute_solution(0, n);
return res == INT32_MAX ? -1 : res;
}
