/**
____ ____ ____ __________________ ____ ____ ____
||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 = (ll)4e18;
std::vector<pll> v[maxn];
int n , k;
ll ans;
ll sumv[maxn];
int 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_min(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_min(ll key) const
{
auto it = store.find(key);
if(it != store.end()) return it->second;
return (ll)4e18;
}
// Merge 'other' into *this*: check complements against this->store,
// then insert other's entries (keeping minimal depths).
// target = k + 2*sum[u], depth_u is dist[u] used in candidate formula.
void _merge_with(component &other, ll target, int depth_u)
{
// check complements (do this before mutating this->store)
for (auto &pr : other.store)
{
ll keyB = pr.X;
ll valB = pr.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;
}
}
// merge other.store into store, keeping minimal depth
for (auto &pr : other.store)
{
ll keyB = pr.X;
ll valB = pr.Y;
auto it = store.find(keyB);
if (it == store.end()) store.emplace(keyB, valB);
else it->second = std::min(it->second, valB);
}
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);
}
};
dsu uni;
// precompute prefix sums and depths, and insert (sum -> depth) into each node's component map
void precomp(int u, int p, ll acc, int depth)
{
sumv[u] = acc;
distv[u] = depth;
uni.un[u].insert_min(acc, depth);
for (auto &ed : v[u])
{
int to = (int)ed.X;
ll w = ed.Y;
if (to == p) continue;
precomp(to, u, acc + w, depth + 1);
}
}
// recursion that uses small-to-large merging; uses component._merge_with to do the actual merge
void small_to_large_merge(int u, int p)
{
ll target = (ll)k + 2LL * sumv[u];
for (auto &ed : v[u])
{
int to = (int)ed.X;
if (to == p) continue;
small_to_large_merge(to, u);
// ensure we merge smaller into larger: if child's map bigger, swap component contents
if (uni.un[to].store.size() > uni.un[u].store.size())
{
uni.un[to]._swap(uni.un[u]);
}
// now merge child's component into parent's component using component member
uni.un[u]._merge_with(uni.un[to], target, distv[u]);
// clear child's map to save memory
uni.un[to].store.clear();
}
}
int best_path(int N, int K, int h[][2], int L[])
{
n = N;
k = K;
ans = INF;
// clear adjacency
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, 0LL, 0);
small_to_large_merge(1, 0);
if (ans == INF) return -1;
return (int)ans;
}
