#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 2> arr;
typedef array<arr, 2> arrr;
constexpr int maxn = 2e5 + 5, maxk = 1e6 + 5;
int n, k;
basic_string <arr> adj[maxn];
int siz[maxn] = { 0 };
bool removed[maxn] = { 0 };
int fnd_size(int p, int par)
{
siz[p] = 1;
for (arr &i : adj[p])
{
if (i[0] == par || removed[i[0]]) continue;
siz[p] += fnd_size(i[0], p);
}
return siz[p];
}
int fnd_centroid(int p, int par, int s)
{
for (arr &i : adj[p])
{
if (i[0] == par || removed[i[0]]) continue;
if (siz[i[0]] * 2 >= s) return fnd_centroid(i[0], p, s);
}
return p;
}
arrr values[maxk] = { 0 };
void fnd_lengths(int p, int par, set<int>&found, int key, int l, int depth)
{
if (l > k) return ;
found.insert(l);
if (values[l][0][0] > depth)
{
if (values[l][0][1] != key) values[l][1] = values[l][0];
values[l][0] = arr{depth, key};
} else if (values[l][0][1] != key && values[l][1][0] > depth)
{
values[l][1] = arr{depth, key};
}
for (arr i : adj[p])
{
if (removed[i[0]] || i[0] == par) continue;
fnd_lengths(i[0], p, found, key, l + i[1], depth + 1);
}
}
int output = 1e9;
void fix(int p)
{
values[p] = arrr{arr{(int)2e9, -1}, arr{(int)2e9, -1}};
}
void centroid_decomp(int p)
{
fnd_size(p, -1);
p = fnd_centroid(p, -1, siz[p]);
removed[p] = true;
/*
Calculate
*/
set <int> found = { 0 };
int key = 0;
for (const arr &i : adj[p])
{
if (removed[i[0]]) continue;
fnd_lengths(i[0], p, found, key++, i[1], 1);
}
values[0][0] = arr{0, -2};
auto it = found.begin();
auto rt = found.rbegin();
while (it != found.end() && rt != found.rend() && *it <= *rt)
{
if (*it + *rt < k) {fix(*it); it++; continue;}
if (*it + *rt > k) {fix(*rt); rt++; continue;}
// cout << "\t" << *it << " " << values[*it][0][0] << " " << *rt << " " << values[*rt][0][0] << "\n";
if (values[*it][0][1] != values[*rt][0][1]) output = min(values[*it][0][0] + values[*rt][0][0], output);
else {
output = min({output, values[*it][0][0] + values[*rt][1][0], values[*rt][0][0] + values[*it][1][0]});
}
fix(*it); fix(*rt);
it++, rt++;
}
// cout << p << " " << output << " " << found.size() << "\n";
// for (int i : found) cout << i << " ";
// cout << "\n";
for (const arr &i : adj[p])
{
if (removed[i[0]]) continue;
centroid_decomp(i[0]);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < n - 1; i++)
{
adj[H[i][0]].push_back(arr{H[i][1], L[i]});
adj[H[i][1]].push_back(arr{H[i][0], L[i]});
}
for (int i = 0; i <= k; i++) fix(i);
int root = 0;
centroid_decomp(root);
if (output == 1e9) return -1;
return output;
}
