#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using pa = pair <ll, ll>;
const int INF = 1e9;
const int N = 2e5;
const int M = 1e6;
int siz[N + 1], dp[M + 1], val[M + 1];
bool removed[N + 1];
vector <pa> g[N + 1];
int n, kk, dep = 0;
void dfs (int node, int parent)
{
siz[node] = 1;
for (auto it : g[node])
if (it.first != parent && !removed[it.first])
{
dfs (it.first, node);
siz[node] += siz[it.first];
}
}
int centroid (int node, int parent, int len)
{
for (auto it : g[node])
if (it.first != parent && !removed[it.first])
{
if (siz[it.first] > (len / 2))
return centroid (it.first, node, len);
}
return node;
}
int dfs1 (int node, int parent, int cost, int edges, int dep, vector <pa> &v)
{
int ans = INF;
int ramas = kk - cost;
if (ramas >= 0 && val[ramas] == dep)
ans = min (ans, edges + dp[ramas]);
if (ramas >= 0)
{
v.push_back({cost, edges});
for (auto it : g[node])
if (it.first != parent && !removed[it.first])
ans = min (ans, dfs1 (it.first, node, cost + it.second, edges + 1, dep, v));
}
return ans;
}
int centroid_decomp (int node, int parent)
{
int ans = INF;
dfs (node, parent);
int len = siz[node];
int c = centroid (node, parent, len);
removed[c] = 1;
++dep;
dp[0] = 0;
val[0] = dep;
///fac pentru un subarbore care are lca centroidul meu
for (auto it : g[c])
if (!removed[it.first])
{
vector <pa> v;
v.clear();
ans = min (ans, dfs1 (it.first, c, it.second, 1, dep, v));
for (auto it1 : v)
if (val[it1.first] != dep || (val[it1.first] == dep && dp[it1.first] > it1.second))
{
val[it1.first] = dep;
dp[it1.first] = it1.second;
}
}
for (auto it : g[c])
if (!removed[it.first])
ans = min (ans, centroid_decomp (it.first, c));
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < n - 1; ++i)
{
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back ({H[i][0], L[i]});
}
kk = K;
for (int i = 0; i < n; ++i)
removed[i] = 0, siz[i] = 0;
for (int i = 0; i <= K; ++i)
dp[i] = val[i] = 0;
int ans = INF;
ans = min (ans, centroid_decomp(0, -1));
if (ans == INF)
ans = -1;
return ans;
}
