#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
vector<pair<int,int>>v[maxn];
map<int,int>mp[maxn]; // {v, dist, min dep}
int dep[maxn], dist[maxn], ans, k;
void check(int v, int depa, int dista)
{
int distb = k+(2*dist[v])-dista;
if(mp[v].count(distb))
{
int depb = mp[v][distb];
ans = min(ans, depa+depb-(2*dep[v]));
}
}
void add(int v, int depa, int dista)
{
if(mp[v].count(dista)) mp[v][dista]=min(mp[v][dista], depa);
else mp[v][dista]=depa;
}
void dfs(int cur, int pa)
{
dep[cur]=dep[pa]+1;
int m = -1;
for(auto [i, c] : v[cur])
{
if(i!=pa)
{
dist[i]= dist[cur]+c;
dfs(i, cur);
if(m==-1|| mp[m].size() < mp[i].size()) m=i;
}
}
if(m!=-1) swap(mp[m], mp[cur]);
check(cur, dep[cur], dist[cur]);
add(cur, dep[cur], dist[cur]);
for(auto [i, c] : v[cur])
{
if(i!=pa&&i!=m)
{
for(auto [dista, depa] : mp[i])
{
check(cur, depa, dista);
}
for(auto [dista, depa] : mp[i])
{
add(cur, depa, dista);
}
}
}
}
int best_path(int n, int K, int h[][2], int l[])
{
k = K;
ans=n;
for(int i = 0; i < n-1; i++)
{
int a = h[i][0], b = h[i][1];
v[a].push_back({b, l[i]});
v[b].push_back({a, l[i]});
}
dfs(0,n);
return (ans==n?-1:ans);
}
