#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
#include "race.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);
const int MAXN = 2 * 1e5 + 5;
const int MAXV = 1e6 + 5;
const int INF = 1e9;
int n;
ll k;
vector<pair<int, int>> adjList[MAXN];
bool found[MAXN];
int idx = -1;
int s[MAXN];
int vals[MAXV];
set<int> used;
int ans = INF;
int tot = 0;
queue<pair<int, int>> add;
void cnt(int src, int p) {
tot++;
for (auto i : adjList[src]) {
if (i.first == p || found[i.first]) {
continue;
}
cnt(i.first, src);
}
}
void centroid(int src, int p) {
s[src] = 1;
int mxVal = 0;
for (auto i : adjList[src]) {
if (i.first == p || found[i.first]) {
continue;
}
centroid(i.first, src);
s[src] += s[i.first];
mxVal = max(mxVal, s[i.first]);
}
if (mxVal <= tot / 2 && tot - s[src] <= tot / 2) {
idx = src;
}
}
void dfs1(int src, int p, int cur, int paths) {
for (auto i : adjList[src]) {
if (i.first == p || found[i.first]) {
continue;
}
int nxt = cur + i.second;
if (nxt > k) {
continue;
}
ans = min(ans, vals[k - nxt] + paths + 1);
add.push({ nxt, paths + 1 });
dfs1(i.first, src, nxt, paths + 1);
if (src == idx) {
while (add.size() > 0) {
int rn = add.front().first;
vals[rn] = min(vals[rn], add.front().second);
used.insert(rn);
add.pop();
}
}
}
}
void dfs(int src, int p) {
idx = -1;
tot = 0;
cnt(src, p);
centroid(src, p);
if (tot == 1) {
return;
}
found[idx] = true;
dfs1(idx, idx, 0, 0);
for (auto i : used) {
vals[i] = INF;
}
used.clear();
for (auto i : adjList[idx]) {
if (i.first == p || found[i.first]) {
continue;
}
dfs(i.first, src);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
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] });
}
for (int i = 0; i < MAXV; i++) {
vals[i] = INF;
}
vals[0] = 0;
dfs(0, 0);
if (ans > n) {
return -1;
}
return ans;
}
