/**
____ ____ ____ __________________ ____ ____ ____
||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;
}
void _swap(component& other)
{
std::swap(sz , other.sz);
store.swap(other.store);
std::swap(dx , other.dx);
}
ll get(ll x)
{
auto it = store.find(x - dx);
if(it != store.end())
return it -> Y;
return INF;
}
void _merge(component& other , ll dd)
{
for(auto& e : other.store)
{
ll a = other.get(e.first + other.dx);
ll b = get(k - e.first - dd - other.dx);
if (a + b < ans) ans = a + b;
}
for(auto& pom : other.store)
{
pll e = pom;
ll newkey = e.first - dd + other.dx - dx;
ll newval = e.second + 1;
auto it = store.find(newkey);
if(it == store.end())
store.emplace(newkey, newval);
else
it->second = std::min(it->second, newval);
}
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 aa , int bb /** child */ , ll w)
{
aa = find_par(aa);
bb = find_par(bb);
if(aa == bb)
return;
component& a = un[aa];
component& b = un[bb];
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 = 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);
if(ans == INF)
return -1;
else
return ans - 1;
}
