#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
map <int, int> m[N];
int shift[N];
int k;
vector <pair <int, int>> g[N];
int res[N];
int h[N];
void prep(int v, int p){
for(auto [x, _] : g[v]){
if(x == p) continue;
h[x] = h[v]+1;
prep(x, v);
}
return;
}
void dfs(int v, int p){
m[v][0] = h[v];
for(auto [x, w] : g[v]){
if(x == p) continue;
dfs(x, v);
shift[x] += w;
if(m[x].size() > m[v].size()){
swap(m[x], m[v]);
swap(shift[x], shift[v]);
}
for(auto [vvalor, altura] : m[x]){
int valor = vvalor;
valor = valor+shift[x];
valor = k-valor;
valor = valor-shift[v];
if(m[v].find(valor) != m[v].end()){
int altura2 = m[v][valor];
cout << altura << ' ' << altura2 << ' ' << v << '\n';
res[v] = min(res[v], altura+altura2-2*h[v]);
}
}
for(auto [vvalor, altura] : m[x]){
int valor = vvalor;
valor = valor+shift[x]-shift[v];
if(m[v].find(valor) != m[v].end()) m[v][valor] = min(m[v][valor], altura);
else m[v][valor] = altura;
}
}
return;
}
int best_path(int n, int K, int h[][2], int l[]){
k = K;
for(int i = 0;i < n-1;i++){
int a = h[i][0], b = h[i][1];
g[a].push_back({b, l[i]});
g[b].push_back({a, l[i]});
}
for(int i = 0;i < n;i++) res[i] = 1e8;
prep(0,0);
dfs(0,0);
int resposta = 1e8;
for(int i= 0;i < n;i++) {
//cout << res[i] << ' ';
resposta = min(resposta, res[i]);
}
return (resposta == 1e8 ? -1 : resposta);
}
