#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int inf = 1e9+9999;
vector<vector<pair<int, int>>> graph;
map<int, int> sums, tempsums;
vector<int> sub;
int k, centroid;
int ans = inf;
int rem;
vector<bool> vis, mark;
int dfs1(int node, int par) {
int val = 1;
mark[node] = true;
for(auto it : graph[node]) {
if(it.first == par)
continue;
if(vis[it.first])
continue;
val += dfs1(it.first, node);
}
sub[node] = val;
return val;
}
void dfs2(int node, int par, int cur, int len) {
if(cur > k)
return;
if(k == cur)
ans = min(ans, len);
else if(sums[k - cur])
ans = min(ans, sums[k - cur] + len);
for(auto it : graph[node]) {
if(vis[it.first])
continue;
if(it.first == par)
continue;
if(node == centroid) {
for(auto it: tempsums) {
if(!sums[it.first])
sums[it.first] = it.second;
sums[it.first] = min(it.second, sums[it.first]);
}
tempsums.clear();
}
dfs2(it.first, node, cur + it.second, len + 1);
}
if(!tempsums[cur])
tempsums[cur] = len;
tempsums[cur] = min(len, tempsums[cur]);
return;
}
int findcentroid(int node, int par, int sz) {
for(auto it : graph[node]){
if(vis[it.first])
continue;
if(it.first == par)
continue;
if(sub[it.first] >= sz / 2)
return findcentroid(it.first, node, sz);
}
return node;
}
int best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
rem = N;
k = K;
graph.assign(N + 5, vector<pair<int, int>>());
vis.assign(N + 5, false);
for(int i = 0; i < N - 1; i++) {
graph[H[i][1]].push_back({H[i][0], L[i]});
graph[H[i][0]].push_back({H[i][1], L[i]});
}
while(rem) {
mark.assign(N + 5, false);
sub.assign(N + 5, 0);
for(int i = 0; i < N; i++) {
sums.clear();
tempsums.clear();
if(mark[i] || vis[i])
continue;
int sz = dfs1(i, -1);
centroid = findcentroid(i, -1, sz);
dfs2(centroid, -1, 0, 0);
vis[centroid] = true;
rem--;
}
}
if(ans == inf)
return -1;
return ans;
}
