#include "race.h"
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
using namespace std;
vector<pair<int, int>> adj[100100];
int ans = 1e9, rt, k;
bool vis[100100];
void csz(vector<int>& sz, int n, int p, int tot) {
int ms = 0;
for (auto i : adj[n])
if (i.first != p && !vis[i.first])
csz(sz, i.first, n, tot), ms = max(ms, sz[i.first]), sz[n]+=sz[i.first];
if (ms <= tot / 2 && sz[n] >= tot / 2)
rt = n;
}
void cans(map<long long, int>& cache, int n, int p, int d1, int d2) {
if (d1 > k)
return;
if (cache.count(k - d1))
ans = min(ans, d2 + cache[k - d1]);
for (auto i : adj[n])
if (i.first != p && !vis[i.first])
cans(cache, i.first, n, d1 + i.second, d2 + 1);
}
void ccache(map<long long, int>& cache, int n, int p, int d1, int d2) {
if (d1 > k)
return;
if (cache.count(d1))
cache[d1] = min(cache[d1], d2);
else
cache[d1] = d2;
for (auto i : adj[n])
if (i.first != p && !vis[i.first])
ccache(cache, i.first, n, d1 + i.second, d2 + 1);
}
void decomp(int n, int tot) {
vector<int> sz(100100, 1);
map<long long, int> cache{ {0,0} };
csz(sz, n, -1, tot);
vis[rt] = 1;
for (auto i : adj[rt])
if (!vis[i.first])
cans(cache, i.first, -1, i.second, 1), ccache(cache, i.first, -1, i.second, 1);
for (auto i : adj[rt])
if (!vis[i.first])
decomp(i.first, sz[i.first]);
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++)
adj[H[i][0]].push_back({ H[i][1], L[i] }), adj[H[i][1]].push_back({ H[i][0], L[i] });
k = K;
decomp(0, N);
return ans==1e9?-1:ans;
}
