#include "race.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 10;
constexpr int K = 1e6 + 10;
constexpr int INF = 1e9 + 10;
struct edge {
int v, c;
};
vector<edge> adj[N] = {};
bool isRemoved[N] = {};
int d[N] = {};
int minPath[N] = {};
int lastUpdated[N] = {};
int curcentroid = 1;
int ans = INF;
int n, k;
int dfs(int node, int pr=-1) {
d[node] = 1;
for (auto ad : adj[node]) {
if (ad.v != pr && !isRemoved[ad.v]) {
d[node] += dfs(ad.v, node);
}
}
return d[node];
}
int getCentroid(int node, int sz, int pr=-1) {
for (auto ad : adj[node]) {
if (ad.v != pr && !isRemoved[ad.v] && d[ad.v] > sz / 2) {
return getCentroid(ad.v, sz, node);
}
}
return node;
}
void update(int node, int cur, int curd, int pr, bool first) {
if (cur > k || curd >= ans) return;
if (first) {
if (lastUpdated[k - cur] == curcentroid) {
ans = min(ans, curd + minPath[k - cur]);
}
}
else {
if (lastUpdated[cur] == curcentroid) {
minPath[cur] = min(curd, minPath[cur]);
}
else {
lastUpdated[cur] = curcentroid;
minPath[cur] = curd;
}
}
for (auto ad : adj[node]) {
if (ad.v != pr && !isRemoved[ad.v]) {
update(ad.v, cur + ad.c, cur + 1, node, first);
}
}
}
void solve(int node) {
curcentroid++;
int centroid = getCentroid(node, dfs(node));
lastUpdated[0] = curcentroid;
minPath[0] = 0;
for (auto ad : adj[centroid]) {
if (!isRemoved[ad.v]) {
update(ad.v, ad.c, 1, centroid, true);
update(ad.v, ad.c, 1, centroid, false);
}
}
isRemoved[centroid] = true;
for (auto ad : adj[centroid]) {
if (!isRemoved[ad.v]) {
solve(ad.v);
}
}
}
int best_path(int nn, int kk, int H[][2], int L[])
{
n = nn, k = kk;
for (int i = 0; i < n - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
solve(0);
if (ans == INF) return -1;
return ans;
}
