#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_K = 1 << 20, inf = 0x3f3f3f3f;
int mn[MAX_K];
void minimise(int& x, int y) {
if (x > y) x = y;
}
int best_path(int N, int K, int H[][2], int L[]) {
vector <vector <int>> graph(N);
for (int i = 0; i < N - 1; ++i) {
graph[H[i][0]].push_back(i);
graph[H[i][1]].push_back(i);
}
vector <int> sub_sz(N), last_v(N, -1), removed(N);
auto Find_Centroid = [&] (int u, int parent, int sz) -> int {
int last = u;
while (true) {
for (int id : graph[u]) {
int v = H[id][0] ^ H[id][1] ^ u;
if (v == parent or removed[v]) continue;
if (sub_sz[v] * 2 > sz) {
last = v; break;
}
}
if (last == u) break;
parent = u; u = last;
}
return last;
};
auto get_size = [&] (auto self, int u, int parent) -> int {
sub_sz[u] = 1;
for (int id : graph[u]) {
int v = H[id][0] ^ H[id][1] ^ u;
if (v == parent or removed[v]) continue;
sub_sz[u] += self(self, v, u);
}
return sub_sz[u];
};
vector <int> pending;
pending.push_back(0);
memset(mn, 0x3f, sizeof mn);
int ans = inf;
vector <int> pref_w(N), depth(N);
vector <int> cache;
auto DFS = [&] (auto self, int u, int parent) -> void {
if (pref_w[u] > K) return;
minimise(ans, depth[u] + mn[K - pref_w[u]]);
cache.push_back(u);
for (int id : graph[u]) {
int v = H[id][0] ^ H[id][1] ^ u;
if (v == parent or removed[v]) continue;
depth[v] = depth[u] + 1;
pref_w[v] = pref_w[u] + L[id];
self(self, v, u);
}
};
auto Build_Centroid = [&] (int u, int parent) -> void {
int cen_node = Find_Centroid(u, parent, get_size(get_size, u, parent));
int l = 0;
removed[cen_node] = true;
depth[cen_node] = 0; pref_w[cen_node] = 0;
mn[0] = 0;
for (int id : graph[cen_node]) {
int v = H[id][0] ^ H[id][1] ^ cen_node;
if (removed[v]) continue;
depth[v] = 1;
pref_w[v] = L[id];
DFS(DFS, v, cen_node);
for (; l < (int) cache.size(); l += 1) {
int& node = cache[l];
minimise(mn[pref_w[node]], depth[node]);
}
}
for (int x : cache) {
mn[pref_w[x]] = inf;
}
cache.clear();
for (int id : graph[cen_node]) {
int v = H[id][0] ^ H[id][1] ^ cen_node;
if (removed[v]) continue;
last_v[v] = cen_node;
pending.push_back(v);
}
};
while (not pending.empty()) {
int u = pending.back(); pending.pop_back();
Build_Centroid(u, last_v[u]);
}
return ans == inf ? -1 : ans;
}
