#include "race.h"
#pragma once
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<pair<int, int> > > graph;
vector<int> lvl;
vector<long long> lvl_cost;
vector<int> weight;
void predfs(int nod, int tata){
for(auto it:graph[nod]){
if(it.first == tata){
continue;
}
lvl[it.first] = 1 + lvl[nod];
lvl_cost[it.first] = it.second + lvl_cost[nod];
predfs(it.first, nod);
weight[nod] += weight[it.first];
}
}
unordered_map<long long, int> mp;
void dfs_add(int nod, int tata){
if(mp.count(lvl_cost[nod]) == 0){
mp[lvl_cost[nod]] = 1 << 30;
}
mp[lvl_cost[nod]] = min(mp[lvl_cost[nod]], lvl[nod]);
for(auto it:graph[nod]){
if(it.first == tata){
continue;
}
dfs_add(it.first, nod);
}
}
int ans_length = (1 << 30);
void dfs_view(int root, int nod, int tata){
long long target = k - (lvl_cost[nod] - lvl_cost[root]) + lvl_cost[nod];
//cerr << root << " " << nod << " with costs " << lvl_cost[root] << " " << lvl_cost[nod] << " looking for " << target << endl;
if(mp.count(target)){
ans_length = min(ans_length, lvl[nod] + mp[target] - 2 * lvl[root]);
//cerr << "ans2 length updated to " << ans_length << endl;
}
for(auto it:graph[nod]){
if(it.first == tata){
continue;
}
dfs_view(root, it.first, nod);
}
}
void dfs(int nod, int tata, bool dump){
int heavyChild = -1;
for(auto it:graph[nod]){
if(it.first == tata){
continue;
}
if(heavyChild == -1 || weight[it.first] > weight[heavyChild]){
heavyChild = it.first;
}
}
for(auto it:graph[nod]){
if(it.first == tata || it.first == heavyChild){
continue;
}
dfs(it.first, nod, true);
}
if(heavyChild != -1){
dfs(heavyChild, nod, false);
}
for(auto it:graph[nod]){
if(it.first == tata || it.first == heavyChild){
continue;
}
dfs_view(nod, it.first, nod);
dfs_add(it.first, nod);
}
if(mp.count(lvl_cost[nod]) == 0){
mp[lvl_cost[nod]] = 1 << 30;
}
mp[lvl_cost[nod]] = min(mp[lvl_cost[nod]], lvl[nod]);
// cerr << nod << "looking down for " << lvl_cost[nod] + k << endl;
// cerr << "big child is " << heavyChild << endl;
// cerr << "level cost is " << lvl_cost[nod] << endl;
// cerr << "k is " << k << endl;
// for(auto it:mp){
// cerr << "debuggg " << it.first << " " << it.second << endl;
// }
if(mp.count(lvl_cost[nod] + k)){
//cerr << "found " << mp[lvl_cost[nod] + k] << endl;
ans_length = min(ans_length, mp[lvl_cost[nod] + k] - lvl[nod]);
// cerr << "ans length updated to " << ans_length << endl;
}
if(dump){
mp.clear();
}
}
int best_path(int _n, int _k, int h[][2], int l[]){
n = _n;
k = _k;
graph = vector<vector<pair<int,int> > >(n + 1, vector<pair<int, int> >());
lvl = vector<int>(n + 1,0);
lvl_cost = vector<long long>(n + 1, 0);
weight = vector<int>(n + 1, 1);
for(int i = 0;i < n - 1;i++){
//cerr << "edge " << h[i][0] + 1 << " " << h[i][1] + 1 << " " << l[i] << endl;
graph[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
graph[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
}
predfs(1, 0);
for(int i = 1;i <= n;i++){
// cerr << "debug " << weight[i] << " " << lvl[i] << " " << lvl_cost[i] << endl;
}
dfs(1, 0, true);
return (ans_length == (1 << 30) ? -1:ans_length);
}
