#include "race.h"
#include <iostream>
#include <vector>
#include <map>
#define int int64_t
using namespace std;
struct coll
{
map<int,int> mp = map<int,int>();
int offs = 0;
bool operator<(const coll& c2)
{
return mp.size() < c2.mp.size();
}
void insert(int id, int v)
{
id -= offs;
if (mp.find(id) != mp.end()) mp.at(id) = min(v, mp.at(id));
else mp.insert(make_pair(id, v));
}
int query(int k)
{
k -= offs;
if (mp.find(k) == mp.end()) return 1e7;
return mp.at(k);
}
static int check(coll& bs, coll& nw, int k, int d)
{
if (bs < nw) swap(bs, nw);
int mn = 1e7;
for (auto p : (nw.mp))
{
int ck = p.first + nw.offs;
if (k < ck) continue;
mn = min(mn, bs.query(k - ck) + p.second - 2*d);
}
return mn;
}
static coll merge(coll& bs, coll& nw)
{
if (bs < nw) swap(bs, nw);
for (auto p : (nw.mp))
{
bs.insert(p.first + nw.offs, p.second);
}
return bs;
}
};
struct tree
{
int n, k;
vector<vector<pair<int,int>>> adjlist;
int res = 1e7;
coll dfs(int curr, int par, int d)
{
coll rt = coll();
rt.insert(0, d);
for (auto p : adjlist[curr])
{
if (p.first == par) continue;
coll nt = dfs(p.first, curr, d + 1);
nt.offs += p.second;
res = min(res, coll::check(nt, rt, k, d));
rt = coll::merge(nt, rt);
}
return rt;
}
};
signed best_path(signed N, signed K, signed H[][2], signed L[])
{
tree t;
t.n = N;
t.k = K;
t.adjlist.resize(N);
for (int i = 0; i < N - 1; i++)
{
t.adjlist[H[i][0]].emplace_back(H[i][1], L[i]);
t.adjlist[H[i][1]].emplace_back(H[i][0], L[i]);
}
t.dfs(0, -1, 0);
return (t.res >= N ? -1 : t.res);
}
