#include <bits/stdc++.h>
using namespace std;
using uint = unsigned;
vector<vector<pair<int, uint>>> adjList; // (vertex, weight)
vector<int> subtrees;
vector<bool> blocked;
vector<pair<uint, uint>> paths;
uint K, N, answer;
template <class T> class flagArray {
public:
flagArray(uint size = 0) : _size(size) { _array = new pair<T, uint>[size]; };
~flagArray() { delete[] _array; };
uint getFlag() const { return _flag; };
void newFlag() { ++_flag; };
pair<T, uint> &operator[](uint idx) { return _array[idx]; };
private:
pair<T, uint> *_array;
uint _flag{0}, _size{0};
};
flagArray<uint> farray(1000001);
inline int dfsFindCentroid(int u, int p) {
subtrees[u] = 1;
for (auto [v, w] : adjList[u])
if (v != p && !blocked[v])
subtrees[u] += dfsFindCentroid(v, u);
return subtrees[u];
}
inline int findCentroid(int u, int p, int n) {
for (auto [v, w] : adjList[u])
if (v != p && !blocked[v] && subtrees[v] > n / 2)
return findCentroid(v, u, n);
return u;
}
inline void dfsPaths(int u, int p, uint dist, uint depth) {
if (dist > K)
return;
paths.push_back({dist, depth});
for (auto [v, w] : adjList[u])
if (v != p && !blocked[v])
dfsPaths(v, u, dist + w, depth + 1);
}
void decompose(int u) {
int centroid = findCentroid(u, -1, dfsFindCentroid(u, -1));
blocked[centroid] = true;
farray.newFlag();
farray[0] = {0, farray.getFlag()};
for (auto [v, w] : adjList[centroid]) {
if (blocked[v])
continue;
paths.clear();
dfsPaths(v, centroid, w, 1);
for (auto [dist, depth] : paths)
if (K >= dist) {
auto p = farray[K - dist];
if (p.second == farray.getFlag())
answer = min(answer, (p.first + depth));
}
for (auto [dist, depth] : paths) {
auto &p = farray[dist];
if (p.second != farray.getFlag() || depth < p.first)
p = {depth, farray.getFlag()};
}
}
for (auto [v, w] : adjList[centroid])
if (!blocked[v])
decompose(v);
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n, K = k, answer = UINT_MAX;
adjList.assign(N, {});
subtrees.assign(N, 0);
blocked.assign(N, false);
for (int i = 0; i < N - 1; i++) {
adjList[H[i][0]].push_back({H[i][1], L[i]});
adjList[H[i][1]].push_back({H[i][0], L[i]});
}
decompose(0);
if (answer == UINT_MAX)
return -1;
return answer;
}
