#include "race.h"
#include <iostream>
#include <vector>
using namespace std;
using pa = pair <int, int>;
const int INF = 1e18;
const int N = 2e5;
const int M = 1e6;
int siz[N + 1], removed[N + 1], tata_c[N + 1], dp[M + 1], h[N + 1][2], l[N + 1], val[M + 1];
vector <pa> g[N + 1];
int n, x, y, k, dep;
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 = k - 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;
tata_c[c] = parent;
++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]});
}
int ans = INF;
ans = min (ans, centroid_decomp(0, -1));
if (ans == INF)
ans = -1;
return ans;
}
