/**
____ ____ ____ __________________ ____ ____ ____
||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;
ll sumv[maxn], distv[maxn];
struct dsu
{
struct component
{
int par, sz;
std::map<ll,ll> store;
void init(int x)
{
par = x;
sz = 1;
store.clear();
}
void _swap(component& other)
{
std::swap(sz, other.sz);
store.swap(other.store);
}
void insert(ll key, ll val)
{
auto it = store.find(key);
if(it == store.end()) store.emplace(key, val);
else it->second = std::min(it->second, val);
}
ll get(ll key)
{
auto it = store.find(key);
if(it != store.end()) return it->second;
return INF;
}
void _merge(component& other, ll target, int depth_u)
{
for(auto &e : other.store)
{
ll keyB = e.X;
ll valB = e.Y;
ll need = target - keyB;
auto it = store.find(need);
if(it != store.end())
{
ll cand = it->second + valB - 2LL * depth_u;
if(cand < ans) ans = cand;
}
}
for(auto &e : other.store)
{
auto it = store.find(e.X);
if(it == store.end()) store.insert(e);
else it->second = std::min(it->second, e.Y);
}
sz += other.sz;
}
};
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 u, int v, int depth_u)
{
u = find_par(u);
v = find_par(v);
if(u == v) return;
component &A = un[u];
component &B = un[v];
ll target = k + 2LL * sumv[u];
if(A.sz < B.sz)
{
std::swap(A, B);
std::swap(u, v);
}
A._merge(B, target, depth_u);
B.par = u;
B.store.clear();
}
};
dsu uni;
void precomp(int u, int p, ll acc, int depth)
{
sumv[u] = acc;
distv[u] = depth;
uni.un[u].store[acc] = depth;
for(auto &nb : v[u])
{
if(nb.X == p) continue;
precomp(nb.X, u, acc + nb.Y, depth + 1);
}
}
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, distv[node]);
}
}
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++)
{
int a = h[i][0] + 1;
int b = h[i][1] + 1;
ll w = L[i];
v[a].PB({b, w});
v[b].PB({a, w});
}
uni.init(n + 5);
precomp(1, 0, 0, 0);
dfs(1, 0);
if(ans == INF) return -1;
return (int)ans;
}
