#include "race.h"
#include <iostream>
#include <vector>
#include <map>
#define int __int128
using namespace std;
using rettype = pair<int,map<int,int>*>;
struct tree
{
int n;
int k;
int res;
vector<vector<pair<int,int>>> adjlist;
tree(int in, int ik) : n(in), k(ik), res(n), adjlist(vector<vector<pair<int,int>>>(n)) {}
void insert(rettype r1, int k, int v)
{
if (r1.second->count(k - r1.first)) (*r1.second)[k - r1.first] = min((*r1.second)[k - r1.first], v);
else (*r1.second)[k - r1.first] = v;
}
int query(rettype rt, int q)
{
if (rt.second->count(q - rt.first)) return (*rt.second)[q - rt.first];
else return 5*n;
}
rettype merge(rettype r1, rettype r2, int d)
{
if (r1.second->size() < r2.second->size()) swap(r1, r2);
for (auto p : (*r2.second))
{
int ck = p.first + r2.first;
res = min(res, query(r1, k - ck) + p.second - 2*d);
insert(r1, ck, p.second);
}
return r1;
}
rettype dfs(int curr, int par, int d)
{
rettype ct = make_pair(0, new map<int,int>());
insert(ct, 0, d);
for (auto next : adjlist[curr])
{
if (next.first == par) continue;
auto nt = dfs(next.first, curr, d + 1);
nt.first += next.second;
ct = merge(ct, nt, d);
}
res = min(query(ct, k) - d, res);
return ct;
}
};
signed best_path(signed N, signed K, signed H[][2], signed L[])
{
tree t(N, K);
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);
}
