#include "race.h"
#include <iostream>
#include <vector>
#include <map>
#define int int64_t
using namespace std;
struct tree
{
int n, k;
int res;
vector<vector<pair<int,int>>> adjlist;
vector<int> sz;
vector<int> lvl;
tree(int in, int ik) : n(in), k(ik), res(2*n), adjlist(vector<vector<pair<int,int>>>(n)), sz(vector<int>(n)), lvl(vector<int>(n, 2*n)) {}
int sdfs(int curr, int par, int l)
{
sz[curr] = 1;
for (auto np : adjlist[curr])
{
int next = np.first;
if (next == par) continue;
if (lvl[next] < l) continue;
sz[curr] += sdfs(next, curr, l);
}
return sz[curr];
}
int centroid(int curr, int par, int tots, int l)
{
for (auto np : adjlist[curr])
{
int next = np.first;
if (next == par) continue;
if (lvl[next] < l) continue;
if (sz[next] > tots / 2) return centroid(next, curr, tots, l);
}
return curr;
}
void decomposition(int rt, int l)
{
sdfs(rt, -1, l);
int cnt = centroid(rt, -1, sz[rt], l);
lvl[cnt] = l;
for (auto np : adjlist[cnt])
{
int next = np.first;
if (lvl[next] > l) decomposition(next, l + 1);
}
}
map<int,int> pths;
map<int,int> newp;
void dfs(int curr, int par, int w, int d, int l)
{
if (d != 0 && lvl[curr] <= l) return;
if (w <= k && pths.find(k - w) != pths.end())
{
res = min(res, d + pths[k - w]);
}
if (newp.find(w) == newp.end()) newp[w] = d;
else newp[w] = min(d, newp[w]);
for (auto np : adjlist[curr])
{
int next = np.first;
if (next != par) dfs(next, curr, w + np.second, d + 1, l);
}
}
void check(int rt)
{
pths.clear();
for (auto np : adjlist[rt])
{
if (lvl[np.first] <= lvl[rt]) continue;
newp.clear();
dfs(np.first, rt, np.second, 1, lvl[rt]);
for (auto p : newp)
{
if (pths.find(p.first) == pths.end()) pths[p.first] = p.second;
else pths[p.first] = min(p.second, pths[p.first]);
}
}
}
};
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.decomposition(0, 0);
for (int i = 0; i < N; i++) t.check(i);
return (t.res >= N ? -1 : t.res);
}
