#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<pair<int, int>> adjlist[200000];
int dist[1000001];
int subsz[200000], level[200000];
vector<pair<int, int>> v;
vector<int> v2;
int k, ans;
void dfs(int x, int p) {
subsz[x] = 1;
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
dfs(i.first, x);
subsz[x] += subsz[i.first];
}
}
int centroid(int x, int p, int treesz) {
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
if (treesz < subsz[i.first] * 2) {
return centroid(i.first, x, treesz);
}
}
return x;
}
void dfs2(int x, int p, int depth, int cost) {
if (cost > k) {
return;
}
v.push_back({cost, depth});
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
dfs2(i.first, x, depth + 1, cost + i.second);
}
}
void decomp(int x) {
dfs(x, -1);
int cent = centroid(x, -1, subsz[x]);
level[cent] = 1;
dist[0] = 0;
for (auto i: adjlist[cent]) {
if (level[i.first] != 0) {
continue;
}
dfs2(i.first, -1, 1, i.second);
for (auto j: v) {
if (dist[k - j.first] == INT_MAX) {
continue;
}
ans = min(ans, dist[k - j.first] + j.second);
}
for (auto j: v) {
v2.push_back(j.first);
dist[j.first] = min(dist[j.first], j.second);
}
v.clear();
}
for (auto i: v2) {
dist[i] = INT_MAX;
}
v2.clear();
for (auto i: adjlist[cent]) {
if (level[i.first] == 0) {
decomp(i.first);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
adjlist[H[i][0]].push_back({H[i][1], L[i]});
adjlist[H[i][1]].push_back({H[i][0], L[i]});
}
k = K;
for (int i = 1; i <= k; i++) {
dist[i] = INT_MAX;
}
ans = N;
decomp(0);
if (ans == N) {
return -1;
} else {
return ans;
}
}
