/**
____ ____ ____ __________________ ____ ____ ____
||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;
// We'll use DFS small-to-large per-node maps (distances measured from the node)
std::map<ll,ll>* mp[maxn];
void dfs_sl(int node, int par)
{
// create map for node: distance 0 -> edges count 0
mp[node] = new std::map<ll,ll>();
mp[node]->emplace(0LL, 0LL);
for (auto &nb : v[node])
{
int to = (int)nb.X;
ll w = nb.Y;
if (to == par) continue;
dfs_sl(to, node);
// ensure mp[node] is the larger map (small-to-large)
if (mp[node]->size() < mp[to]->size())
{
// swap pointers: node's map becomes child's map and vice versa
std::swap(mp[node], mp[to]);
// the map now in mp[node] has distances relative to 'to' not 'node'
// shift all keys in mp[node] by +w and add +1 to values (edges count)
std::map<ll,ll>* shifted = new std::map<ll,ll>();
for (auto &pr : *mp[node])
{
ll newd = pr.first + w;
ll newv = pr.second + 1;
auto it = shifted->find(newd);
if (it == shifted->end()) shifted->emplace(newd, newv);
else it->second = std::min(it->second, newv);
}
delete mp[node];
mp[node] = shifted;
}
else
{
// mp[node] is the larger; merge mp[to] into mp[node]
// query complements first
for (auto &pr : *mp[to])
{
ll dist_from_node = pr.first + w;
ll edges_cnt = pr.second + 1;
ll need = (ll)k - dist_from_node;
auto it = mp[node]->find(need);
if (it != mp[node]->end())
ans = std::min(ans, it->second + edges_cnt);
}
// insert shifted entries
for (auto &pr : *mp[to])
{
ll newd = pr.first + w;
ll newv = pr.second + 1;
auto it = mp[node]->find(newd);
if (it == mp[node]->end()) mp[node]->emplace(newd, newv);
else it->second = std::min(it->second, newv);
}
delete mp[to];
mp[to] = nullptr;
continue;
}
// after swapping, merge the smaller map (old mp[to]) into new mp[node]
for (auto &pr : *mp[to])
{
ll dist_from_node = pr.first + w;
ll edges_cnt = pr.second + 1;
auto it = mp[node]->find((ll)k - dist_from_node);
if (it != mp[node]->end())
ans = std::min(ans, it->second + edges_cnt);
}
for (auto &pr : *mp[to])
{
ll newd = pr.first + w;
ll newv = pr.second + 1;
auto it = mp[node]->find(newd);
if (it == mp[node]->end()) mp[node]->emplace(newd, newv);
else it->second = std::min(it->second, newv);
}
delete mp[to];
mp[to] = nullptr;
}
// check if there's a path of distance exactly k within subtree
auto it = mp[node]->find((ll)k);
if (it != mp[node]->end())
ans = std::min(ans, it->second);
}
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)
{
v[h[i][0] + 1].PB({h[i][1] + 1, L[i]});
v[h[i][1] + 1].PB({h[i][0] + 1, L[i]});
}
for (int i = 0; i <= n; ++i) mp[i] = nullptr;
dfs_sl(1, 0);
if (mp[1]) { delete mp[1]; mp[1] = nullptr; }
if (ans == INF) return -1;
else return (int)ans; // ans stores number of edges directly
}
