/**
____ ____ ____ __________________ ____ ____ ____
||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_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);
}
void _merge(component &other , ll target , ll depth_u)
{
// check all possible pairs
for(auto &e : other.store)
{
ll keyB = e.X , 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;
}
}
// merge maps (keeping minimal depths)
for(auto &e : other.store)
{
ll key = e.X , val = e.Y;
auto it = store.find(key);
if(it == store.end())
store.emplace(key , val);
else
it->second = std::min(it->second , val);
}
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 , ll depth_u)
{
u = find_par(u);
v = find_par(v);
if(u == v)
return;
ll target = k + 2LL * sumv[u];
component &A = un[u];
component &B = un[v];
// ensure A is the larger one
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;
else
return (int)ans;
}
