#include "race.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <unordered_map>
#include <cassert>
using namespace std;
const int MAX_N = 5e5 + 10;
bool used[MAX_N];
int subtree[MAX_N], dist[MAX_N], height[MAX_N];
int h[MAX_N][2], l[MAX_N];
int KK;
int ans = MAX_N;
vector <vector<pair<int, int>>> G;
int find_centroid(int v) {
int p = -1;
int u = v;
while (1) {
int x = -1;
for (auto it : G[u]) {
if (it.first == p) continue;
if (used[it.first]) continue;
if (2 * subtree[it.first] > subtree[v]) {
x = it.first;
break;
}
}
if (x == -1) return u;
p = u;
u = x;
}
}
void dfs(int v, int p) {
if (p == -1) {
dist[v] = 0;
height[v] = 0;
}
subtree[v] = 1;
for (auto it : G[v]) {
if (it.first == p || used[it.first]) continue;
dist[it.first] = min(dist[v] + it.second, KK + 1);
height[it.first] = height[v] + 1;
dfs(it.first, v);
subtree[v] += subtree[it.first];
}
}
vector <int> vec;
void find_vertexes(int v, int p) {
vec.push_back(v);
for (auto it : G[v]) {
if (used[it.first] || it.first == p) continue;
find_vertexes(it.first, v);
}
}
void solve(int v) {
dfs(v, -1);
v = find_centroid(v);
dfs(v, -1);
vector <vector<int>> u;
for (auto it : G[v]) {
if (used[it.first]) continue;
vec.clear();
find_vertexes(it.first, v);
u.push_back(vec);
}
unordered_map <int, int> mp;
for (auto it : u) {
for (auto j : it) {
if (mp.find(KK - dist[j]) != mp.end()) {
ans = min(ans, height[j] + mp[KK - dist[j]]);
}
}
for (auto j : it) {
if (mp.find(dist[j]) == mp.end()) {
mp[dist[j]] = height[j];
}
else mp[dist[j]] = min(mp[dist[j]], height[j]);
}
}
if (mp.find(KK) != mp.end()) {
ans = min(ans, mp[KK]);
}
used[v] = true;
for (auto it : G[v]) {
if (used[it.first]) continue;
solve(it.first);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
KK = K;
G.resize(N);
for (int i = 0; i < N - 1; i++) {
G[H[i][0]].push_back({ H[i][1], L[i] });
G[H[i][1]].push_back({ H[i][0], L[i] });
}
solve(0);
if (ans == MAX_N) return -1;
return ans;
}
//int main() {
// int n, k;
// cin >> n >> k;
// for (int i = 0; i < n - 1; i++) {
// cin >> h[i][0] >> h[i][1];
// }
// for (int i = 0; i < n - 1; i++) {
// cin >> l[i];
// }
// cout << best_path(n, k, h, l) << "\n";
//}
