#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
int min(int x, int y){
if (x < y) return x;
return y;
}
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
vector<map<int, int>> m;
vector<int> root;
vector<int> dist;
vector<vector<pair<int, int>>> graph;
int answer = 100; int T;
set<int> q;
void dfs(int s, int p){
int target = T+2*root[s];
for (auto [node, weight]: graph[s]){
if (node == p) continue;
dfs(node, s);
if (m[node].size() > m[s].size()) swap(m[node], m[s]);
for (auto x: m[node]){
// cout << target-x.first << endl;
if (m[s].find(target-x.first) != m[s].end()){
answer = min(answer, m[s][target-x.first] + x.second - 2*dist[s]);
q.insert(m[s][target-x.first] + x.second - 2*dist[s]);
// cout << "a" << answer << endl;
}
}
for (auto x: m[node]){
if (x.second == 0) continue;
// if (s == 1 && x.first == 9) cout << node << endl;
if (m[s].find(x.first) == m[s].end()){
m[s].insert(x);
}else{
m[s][x.first] = min(m[s][x.first], x.second);
}
}
}
int targ = T+root[s];
if (m[s].find(targ) != m[s].end()){
// if (s == 1) cout <<"a" << target << endl;
q.insert(m[s][targ]-dist[s]);
// cout << s << endl;
}
}
int best_path(int N, int K, int H[][2], int L[])
{
T = K;
// cout << "a" << endl;
dist.resize(N+1);
root.resize(N+1);
graph.resize(N+1);
m.resize(N+1);
FOR(i,0,N-1){
graph[H[i][0]].pb({H[i][1], L[i]});
graph[H[i][1]].pb({H[i][0], L[i]});
}
stack<int> s;
s.push(0);
vector<int> visited(N+1);
while (!s.empty()){
int current = s.top();
s.pop();
if (visited[current]) continue;
for (auto [x, w]: graph[current]){
if (visited[x]) continue;
root[x] = root[current]+w;
dist[x] = dist[current]+1;
m[x][root[x]] = dist[x];
s.push(x);
}
visited[current] = 1;
}
// printVector(root);
// printVector(dist);
dfs(0, -1);
if (!q.size()) return -1;
// for (auto x: q){
// cout << x << endl;
// }
return *q.begin();
}
