#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
int K, N, res, curr_maks, curr_node, cnt, ans;
vector<vii> adjList(200001);
vi subtree, gotov, mini, moze;
void cal_subtree(int curr, int prev){
int D = 0;
for (int i = 0; i < adjList[curr].size(); i++){
int t = adjList[curr][i].first;
if (t != prev && !gotov[t]){
cal_subtree(t, curr);
D += 1 + subtree[t];
}
}
subtree[curr] = D;
}
void find_centr(int curr, int prev, int uk){
int x = uk - subtree[curr] - 1;
for (int i = 0; i < adjList[curr].size(); i++){
int t = adjList[curr][i].first;
if (t != prev && !gotov[t]){
find_centr(t, curr, uk);
x = max(x, 1 + subtree[t]);
}
}
if (curr_maks > x){
curr_node = curr;
curr_maks = x;
}
}
void dfs1(int curr, int prev, int dist, int depth){
if (dist > K)
return;
if (moze[dist] != cnt || depth < mini[dist]){
moze[dist] = cnt;
mini[dist] = depth;
}
for (int i = 0; i < adjList[curr].size(); i++){
int t = adjList[curr][i].first;
if (t != prev && !gotov[t])
dfs1(t, curr, dist + adjList[curr][i].second, depth + 1);
}
}
void dfs2(int curr, int prev, int dist, int depth){
if (dist > K)
return;
//cout << curr << " " << prev << " " << dist << endl;
if (moze[K - dist] == cnt){
ans = min(ans, depth + mini[K - dist]);
//cout << curr << " " << prev << " " << dist << endl;
}
if (K == dist){
ans = min(ans, depth);
//cout << curr << " " << prev << " " << dist << endl;
}
for (int i = 0; i < adjList[curr].size(); i++){
int t = adjList[curr][i].first;
if (t != prev && !gotov[t])
dfs2(t, curr, dist + adjList[curr][i].second, depth + 1);
}
}
void solve(int curr){
cal_subtree(curr, -1);
if (subtree[curr] <= 1)
return;
curr_node = -1; curr_maks = INT_MAX;
find_centr(curr, -1, subtree[curr] + 1);
int centr = curr_node;
//cout << centr << endl;
cnt++;
for (int i = 0; i < adjList[centr].size(); i++){
int t = adjList[centr][i].first;
if (!gotov[t]){
dfs2(t, centr, adjList[centr][i].second, 1);
dfs1(t, centr, adjList[centr][i].second, 1);
}
}
//1. i 2. dfs
gotov[centr] = true;
for (int i = 0; i < adjList[centr].size(); i++){
int t = adjList[centr][i].first;
if (!gotov[t])
solve(t);
}
}
int best_path(int n, int k, int h[][2], int l[]){
res = INT_MAX;
N = n; K = k;
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]});
}
gotov.assign(n +1 , false);
mini.assign(k + 1, 0);
subtree.assign(n + 1, 0);
moze.assign(k + 1, -1);
cnt = 0;
ans = INT_MAX;
solve(0);
if (ans == INT_MAX)
return -1;
return ans;
}
