#include "race.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <utility>
#include <vector>
// #include <algo.hpp>
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
struct CentroiddeComposition {
int _n_, _k_, _ans_;
vector<vector<pair<int, int>>> g;
vector<bool> removed;
vector<int> subSize, distFromCentroid, nodeFromCentroid;
vector<vector<int>> level;
map<int, int> mp;
CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi) {
removed.assign(_n + 1, false);
distFromCentroid.assign(_n + 1, INFi);
nodeFromCentroid.assign(_n + 1, INFi);
subSize.resize(_n + 1);
level.resize(_n + 1);
}
int getSubSize(int v, int pa = -1) {
subSize[v] = 1;
for (const auto &[u, w] : g[v]) {
if (u == pa || removed[u])
continue;
getSubSize(u, v);
subSize[v] += subSize[u];
}
return subSize[v];
}
void getDistFromCentroid(int v, int pa) {
if (distFromCentroid[v] > _k_) // XXX: it can be in the same subtree
return;
// INFO: is it in other side of centroid???
if (distFromCentroid[v] <= _k_) {
int target = _k_ - distFromCentroid[v];
if (mp.find(target) != mp.end()) {
_ans_ = min(_ans_, mp[target] + nodeFromCentroid[v]);
}
if (mp.find(distFromCentroid[v]) == mp.end())
mp[distFromCentroid[v]] = nodeFromCentroid[v];
mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]);
}
for (const auto &[u, w] : g[v]) {
if (pa == u || removed[u])
continue;
distFromCentroid[u] = distFromCentroid[v] + w;
nodeFromCentroid[u] = nodeFromCentroid[v] + 1;
getDistFromCentroid(u, v);
}
}
int findCentroid(int v, int half, int pa = -1) {
for (const auto &[u, w] : g[v]) {
if (u == pa || removed[u] || subSize[u] <= half) {
continue;
}
return findCentroid(u, half, v);
}
return v;
}
int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
// WARNING: You must initilaze before getDistFromCentroid Manualy
// nodeFromCentroid[v] = 0;
// distFromCentroid[v] = 0;
// mp.clear();
// mp_same.clear();
// getDistFromCentroid(v, -1);
nodeFromCentroid[centroid] = 0;
distFromCentroid[centroid] = 0;
mp.clear();
mp[0] = 0;
getDistFromCentroid(centroid, -1);
return _ans_;
}
int build(int v = 0, int id = 0) { // TODO: Inside
int centroid = findCentroid(v, getSubSize(v) >> 1);
removed[centroid] = true;
solve(centroid, subSize[v]);
for (const auto &[u, w] : g[centroid]) {
if (removed[u])
continue;
level[id + 1].push_back(build(u, id + 1)); // WARNING: should it be id + 1 or id ???
}
return centroid;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
// return 0;
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < N - 1; i++) {
const int &u = H[i][0], &v = H[i][1], &w = L[i];
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
CentroiddeComposition t(N, g, K);
t.level[0].push_back(t.build(0));
if (t._ans_ == INFi)
t._ans_ = -1;
return t._ans_;
}
// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
