#include <bits/stdc++.h>
#include "race.h"
using namespace std;
struct node
{
size_t u, s; // id, number of edges to the centroid.
};
vector<vector<pair<size_t, long>>> g;
vector<size_t> subtr_size;
vector<bool> visited;
map<size_t, pair<node, node>> paths;
vector<pair<node, long>> cdis;
size_t min_path = SIZE_MAX;
size_t get_size(size_t u, size_t p)
{
size_t total = 1;
for (auto const &[v, w] : g[u])
if (!visited[v] && v != p)
total += get_size(v, u);
subtr_size[u] = total;
return total;
}
size_t find_centroid(size_t u, size_t p, size_t n)
{
for (auto const &[v, w] : g[u])
if (!visited[v] && v != p && subtr_size[v] > n / 2)
return find_centroid(v, u, n);
return u;
}
void find_path_lengths(size_t u, size_t p = -1, size_t l = 0, size_t h = 0)
{
auto it = paths.find(l);
if (it == paths.end())
paths[l] = make_pair((node){u, h}, (node){0, SIZE_MAX});
else
{
if (h < it->second.first.s)
{
it->second.second = it->second.first;
it->second.first = {u, h};
}
else if (h < it->second.second.s)
{
it->second.second = {u, h};
}
}
for (auto const &[v, w] : g[u])
if (!visited[v] && v != p)
find_path_lengths(v, u, l + w, h + 1);
}
void find_cdis(size_t u, size_t p = -1, size_t l = 0, size_t h = 0)
{
cdis.push_back(make_pair((node){u, h}, l));
for (auto const &[v, w] : g[u])
if (!visited[v] && v != p)
find_cdis(v, u, l + w, h + 1);
}
void decompose(size_t u, size_t k)
{
size_t n = get_size(u, -1);
size_t c = find_centroid(u, -1, n);
visited[c] = 1;
// Search for all path lengths <= k in each adjacent subtree of the current centroid.
// If possible, match them up and update the current minimum.
paths[0] = make_pair((node){c, 0}, (node){0, SIZE_MAX});
for (auto const &[v, w] : g[c])
{
find_cdis(v, c, w, 1);
for (auto const &[x, l] : cdis)
{
auto it = paths.find(k - l);
if (it != paths.end())
{
if (it->second.first.u == x.u)
{
if (it->second.second.s != SIZE_MAX)
min_path = min(min_path, it->second.second.s + x.s);
}
else
{
min_path = min(min_path, it->second.first.s + x.s);
}
}
}
cdis.clear();
find_path_lengths(v, c, w, 1);
}
paths.clear();
for (auto const &[v, w] : g[c])
{
if (!visited[v])
{
decompose(v, k);
}
}
}
int best_path(int n, int k, int edges[][2], int length[])
{
if (n == 1)
return -1;
g = vector<vector<pair<size_t, long>>>(n);
for (size_t i = 0; i < n - 1; i++)
{
g[edges[i][0]].push_back({edges[i][1], length[i]});
g[edges[i][1]].push_back({edges[i][0], length[i]});
}
subtr_size = vector<size_t>(n);
visited = vector<bool>(n, 0);
cdis = vector<pair<node, long>>(n);
decompose(0, k);
if (min_path == SIZE_MAX)
return -1;
return min_path;
}
