#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>
#include "race.h"
int gs, tgt;
std::vector<std::vector<std::pair<int,int>>> adj_list;
int depth[200005];
int64_t dist[200005];
void dfs1(int k, int p) {
for (const auto& [i, w] : adj_list[k]) {
if (i!=p) {
depth[i] = depth[k]+1;
dist[i] = dist[k] + w;
dfs1(i,k);
}
}
}
std::set<std::pair<int64_t,int>> dfs2(int k, int p, int& ans) {
std::set<std::pair<int64_t,int>> ret;
ret.emplace(dist[k], depth[k]);
for (const auto& [i, w] : adj_list[k]) {
if (i!=p) {
auto tmp = dfs2(i,k,ans);
if (ret.size()<tmp.size()) {
std::swap(ret,tmp);
}
for (const auto& a : tmp) {
if (a.first-dist[k]==tgt) {
ans = std::min(ans, a.second-depth[k]);
}
auto b = ret.lower_bound(std::pair<int64_t,int>(tgt-a.first+2*dist[k],0));
if (b==ret.end()) {
continue;
}
if (b->first==tgt-a.first+2*dist[k]) {
ans = std::min(ans, a.second+b->second-2*depth[k]);
}
}
for (const auto& it : tmp) {
ret.emplace(it);
}
}
}
return ret;
}
int best_path(int N, int K, int H[][2], int L[]) {
gs = N;
tgt = K;
adj_list.clear(); adj_list.resize(gs+1);
for (int i = 0; i < gs-1; i++) {
adj_list[H[i][0]].emplace_back(H[i][1], L[i]);
adj_list[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs1(0,-1);
int ret = 0x3f3f3f3f; dfs2(0,-1,ret);
if (ret == 0x3f3f3f3f) {
return -1;
}
return ret;
}
