#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MP make_pair
int K, ans;
vector<vector<pair<int, int>>> edge;
vector<pair<int, int>> dfs(int u, int par)
{
multiset<pair<int, int>> ms;
vector<vector<pair<int, int>>> rets;
for (auto &[v, w] : edge[u])
if (v != par)
{
vector<pair<int, int>> ret = dfs(v, u);
for (auto &p : ret)
{
p.F += w, p.S++;
ms.insert(p);
if (p.F == K)
ans = min(ans, p.S);
}
rets.push_back(ret);
}
for (auto &v : rets)
{
for (auto &p : v)
ms.erase(ms.find(p));
for (auto &p : v)
{
auto it = ms.lower_bound(make_pair(K - p.first, 0));
if (it != ms.end() && it -> first == K - p.first)
ans = min(ans, p.second + it -> second);
}
for (auto &p : v)
ms.insert(p);
}
vector<pair<int, int>> ret;
ret.push_back(make_pair(0, 0));
for (auto it = ms.begin(); it != ms.end(); )
{
ret.push_back(*it);
auto jt = it;
while (jt != ms.end() && it -> first == jt -> first)
jt++;
it = jt;
}
return ret;
}
int best_path(int N, int K_, int H[][2], int L[])
{
K = K_;
edge.resize(N);
for (int i = 0; i + 1 < N; i++)
{
edge[H[i][0]].push_back(MP(H[i][1], L[i]));
edge[H[i][1]].push_back(MP(H[i][0], L[i]));
}
ans = N, dfs(0, 0);
return ans == N ? -1 : ans;
}
