#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int N = 2e5+5, W = 1e6+5, inf = 1e9;
int n, k, sz[N];
int lmin[W], ans;
bool del[N];
vector<pair<int,int>> adj[N];
int Size(int x, int t = -1)
{
sz[x] = 1;
for (auto [y, _] : adj[x])
{
if (y == t || del[y]) continue;
sz[x] += Size(y, x);
}
return sz[x];
}
int Centroid(int x, int size, int t = -1) // O(log(size))
{
for (auto [y, _] : adj[x])
{
if (y == t || del[y]) continue;
if (2 * sz[y] > size)
return Centroid(y, size, x);
}
return x;
}
queue<int> q;
stack<pair<int, int>> path;
// parcurg numai subarborele centroidului cen (x)
// la terminarea fiecarul nod x (care nu e centroidul de plecare), plasez in stiva <distanta, h> fata de centroid
// Toate lanturile trebuie sa treaca prin centroid. La descoperirea lui x, utilizez lmin[k - we] obtinut fara participarea vreunui nod din subarborele cu rad in fiul curent al centroidului,
void Dfs(int x, int t, int we = 0, int d = 0) // subarbore care il contine si pe x
{
if (we > k || d > ans) return;
if (d < lmin[we])
{
lmin[we] = d;
q.push(we);
}
// [k - we] + we
if (lmin[k - we] != inf) // daca lantul merge: y -- centroid -- x
ans = min(ans, lmin[k - we] + d); // lanturi care traverseaza centroidul
for (auto [y, w] : adj[x])
{
if (del[y] || y == t) continue;
Dfs(y, x, we + w, d + 1);
}
}
void Decompose(int x)
{
int cen = Centroid(x, Size(x));
del[cen] = true;
Dfs(cen, -1);
while (!q.empty())
lmin[q.front()] = inf;
for (auto [y, _] : adj[cen])
if (!del[y])
Decompose(y);
}
int best_path(int N, int K, int H[][2], int L[]) // prototipul este obligatoriu
{
n = N, k = K;
for (int i = 0; i < n-1; i++)
{
int x = H[i][0] + 1, y = H[i][1] + 1, w = L[i]; // renumerotare noduri de la 1
adj[x].emplace_back(y, w);
adj[y].emplace_back(x, w);
}
ans = inf;
for(int i = 1; i <= k; i++) // important! lmin[0] = 0
lmin[i] = inf;
Decompose(1);
return ans == inf ? -1 : ans;
}
