#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
long long n, k;
vector<pii> adjlist[200000];
long long dep[200000];
long long off[200000];
long long ans = 1<<30;
set<pii> *dfs(long long n, long long p, long long d){
dep[n] = d;
set<pii> *cur = new set<pii>();
for (auto [i, cost] : adjlist[n]){
if (i == p) continue;
set<pii> *child = dfs(i, n, d + 1);
if (cur->size() < child->size()){
for (auto [path, depth] : *cur){
auto itr = child->lower_bound({k - (path + off[n]) - cost - off[i], 0});
if (itr != child->end()){
if ((*itr).first == k - (path + off[n]) - cost - off[i]){
ans = min(ans, (*itr).second + depth - 2*d);
}
}
}
for (auto [path, depth] : *cur){
long long newp = path + off[n] - off[i] - cost;
child->insert({newp, depth});
}
off[n] = off[i] + cost;
swap(child, cur);
} else {
for (auto [path, depth] : *child){
long long actual = path + off[i] + cost;
auto itr = cur->lower_bound({k - actual - off[n], 0});
if (itr != cur->end()){
if ((*itr).first == k - actual - off[n]){
ans = min(ans, (*itr).second + depth - 2*d);
}
}
}
for (auto [path, depth] : *child){
cur->insert({path + off[i] + cost - off[n], depth});
}
}
}
cur->insert({-off[n], d});
auto itr = cur->lower_bound({k - off[n], 0});
if (itr != cur->end()){
if ((*itr).first == k - off[n]){
ans = min(ans, (*itr).second - d);
}
}
return cur;
}
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]});
}
dfs(0, -1, 0);
if (ans == (1<<30)) return -1;
else return ans;
}
