#include "race.h"
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;
vector<pair<int, int>> graf[200005];
bool rmv[200005];
int sz[200005];
int rez = -1;
int k = 0;
int sbsz(int u, int p)
{
sz[u] = 1;
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
sz[u] += sbsz(v, u);
}
return sz[u];
}
int gct(int u, int vel, int p)
{
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
if (sz[v]*2 > vel)
return gct(v, vel, u);
}
return u;
}
void dfs(unordered_map<int, int>& mp, vector<pair<int, int>>& nv, int u, int tr, int gl, int p = -1)
{
if (tr > k)
return;
// cout << "-> " << gl << " " << u << " " << tr << "\n";
nv.push_back({tr, gl});
if (mp.find(k-tr) != mp.end())
{
rez = min((rez == -1 ? gl + mp[k-tr] : rez), gl + mp[k-tr]);
// cout << u << " " << tr << " " << gl << "\n";
}
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
dfs(mp, nv, v, tr+w, gl+1, u);
}
}
void decom(int u)
{
int ct = gct(u, sbsz(u, -1), -1);
unordered_map<int, int> mp;
mp[0] = 0;
for (auto [v, w] : graf[ct])
{
if (rmv[v])
continue;
vector<pair<int, int>> nv;
dfs(mp, nv, v, w, 1, u);
for (auto [x, y] : nv)
{
if (mp.find(x) == mp.end())
mp[x] = y;
else
mp[x] = min(mp[x], y);
}
}
rmv[ct] = 1;
for (auto [v, w] : graf[ct])
if (!rmv[v])
decom(v);
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
int n = N;
k = K;
for (int i = 0; i < n-1; i++)
{
int u = H[i][0], v = H[i][1];
int w = L[i];
// cout << "--> " << u << " " << v << " " << w << "\n";
graf[u].push_back({v, w});
graf[v].push_back({u, w});
}
decom(0);
return rez;
}
