#include "race.h"
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
using namespace std;
#define int long long
#define inf 1000000000
vector<pair<int, int>> adj[200100];
int ans = inf, rt, k, sz[200100];
bool vis[200100];
map<int, int> cache;
void csz(int n, int p, int tot) {
int ms = 0;
sz[n] = 1;
for (auto &i : adj[n])
if (i.first != p && !vis[i.first])
csz(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(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(i.first, n, d1 + i.second, d2 + 1);
}
void ccache(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(i.first, n, d1 + i.second, d2 + 1);
}
void decomp(int n, int tot) {
vector<int> v;
cache.clear();
cache[0];
csz(n, -1, tot);
n = rt;
vis[n] = 1;
for (auto &i : adj[n]) {
if (!vis[i.first])
cans(i.first, -1, i.second, 1), ccache(i.first, -1, i.second, 1);
v.push_back(sz[i.first]);
}
int x = 0;
for (auto &i : adj[n]) {
if (!vis[i.first])
decomp(i.first, v[x]);
x++;
}
}
signed best_path(signed N, signed K, signed H[][2], signed 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(1, N);
return ans == inf ? -1 : ans;
}
