/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <vector>
#include <map>
#include "race.h"
#define maxn 500005
#define PB push_back
#define X first
#define Y second
typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll INF = 4e18;
std::vector<pll> v[maxn];
int n, k;
ll ans;
struct dsu
{
struct component
{
int par, sz;
std::map<ll,ll> store;
ll dx;
void init(int x)
{
par = x;
sz = 1;
store.clear();
store[0] = 1;
dx = 0;
}
ll get(ll x)
{
auto it = store.find(x - dx);
if(it != store.end()) return it->Y;
return INF;
}
void _merge(component& other, ll w)
{
for(auto &e : other.store)
{
ll realB = e.X + other.dx;
ll needA = k - realB - w;
ll valB = e.Y;
ll valA = get(needA);
if(valA != INF)
ans = std::min(ans, valA + valB);
}
for(auto &e : other.store)
{
ll realB = e.X + other.dx + w;
ll keyA = realB - dx;
ll val = e.Y + 1;
auto it = store.find(keyA);
if(it == store.end())
store[keyA] = val;
else
it->second = std::min(it->second, val);
}
sz += other.sz;
other.par = par;
}
};
std::vector<component> un;
void init(int sz)
{
un.resize(sz + 1);
for(int i = 1; i <= n; i++)
un[i].init(i);
}
int find_par(int node)
{
return node == un[node].par ? node : un[node].par = find_par(un[node].par);
}
void unite(int a, int b, ll w)
{
a = find_par(a);
b = find_par(b);
if(a == b) return;
component &A = un[a];
component &B = un[b];
if(A.sz < B.sz)
{
B._merge(A, w);
}
else
{
A._merge(B, w);
}
}
};
dsu uni;
void dfs(int node, int par)
{
for(auto &nb : v[node])
{
if(nb.X == par) continue;
dfs(nb.X, node);
uni.unite(node, nb.X, nb.Y);
}
}
int best_path(int N, int K, int h[][2], int L[])
{
n = N;
k = K;
ans = INF;
for(int i = 1; i <= n; i++) v[i].clear();
for(int i = 0; i < n - 1; i++)
{
v[h[i][0] + 1].PB({h[i][1] + 1, L[i]});
v[h[i][1] + 1].PB({h[i][0] + 1, L[i]});
}
uni.init(n + 5);
dfs(1, 0);
return (ans == INF ? -1 : (int)(ans - 1));
}
