#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define taskname "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 2e5 + 5;
typedef pair<int,int> tpair;
int n , sz[maxn] , h[maxn] , k;
int res = maxn;
vector<tpair> v[maxn];
unordered_map<ll,int> *vec[maxn];
ll dep[maxn];
void DFS1(int u , int p)
{
sz[u] = 1;
for(tpair c : v[u])
{
if(p == c.first)continue;
h[c.first] = h[u] + 1;
dep[c.first] = dep[u] + c.second;
DFS1(c.first,u);
sz[u] += sz[c.first];
}
}
void add(unordered_map<ll,int> & s , int h1 , ll d1 , int& h , ll& d , int type)
{
if(type == 1)
{
ll need = k - d1 + 2 * d;
if(!s.count(need))return;
res = min(res ,s[need] + h1 - 2 * h);
}
else {
if(!s.count(d1))
{
s[d1] = h1;
return;
}
int tmp = s[d1];
if(tmp > h1)s[d1] = h1;
}
}
void DSU(int u , int p)
{
int bigchild = -1;
for(auto c : v[u])
if(c.first != p && (bigchild == -1 || sz[bigchild] < sz[c.first]))
bigchild = c.first;
for(auto c : v[u])
if(c.first != p && c.first != bigchild)
DSU(c.first , u);
if(bigchild != -1)
{
DSU(bigchild , u);
vec[u] = vec[bigchild];
}
else vec[u] = new unordered_map<ll,int>;
add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 0);
add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 1);
for(auto c : v[u])
if(c.first != p && c.first != bigchild){
for(auto d : (*vec[c.first]))
add(*vec[u] , d.second , d.first , h[u] , dep[u] , 1);
for(auto d : (*vec[c.first]))
add(*vec[u] , d.second , d.first , h[u] , dep[u] , 0);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;k = K;
for(int i = 0 ; i < n - 1 ; ++i){
int a = H[i][0] , b = H[i][1] , c = L[i];
++a;++b;
v[a].pb({b,c});
v[b].pb({a,c});
}
DFS1(1 ,0);
DSU(1 ,0);
if(res == maxn)return -1;
else return res;
}
