#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
vector<int> dp(N), sum(N);
vector<bool> rem(N, false);
function<int(int, int)> dfs_sz = [&](int x, int p) {
int res = 1;
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
res += dfs_sz(u, x);
}
return dp[x] = res;
};
function<int(int, int)> dfs_sum = [&](int x, int p) {
int res = 0;
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
res += w + dfs_sum(u, x);
}
return res;
};
function<int(int, int, int)> centroid = [&](int x, int p, int sz) {
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
if (dp[u] * 2 > sz) return centroid(u, x, sz);
}
return x;
};
pair<int, int> ans = {1e9, 0};
function<void(int)> build = [&](int x) {
int cen = centroid(x, -1, dfs_sz(x, -1));
if (dfs_sum(cen, -1) < K) { rem[cen] = true; return; }
rem[cen] = true;
map<int, pair<int, int>> mn;
queue<tuple<int, int, int, int>> q;
mn[0] = {0, 1};
for (auto &[u, w] : adj[cen]) {
if (rem[u]) continue;
map<int, pair<int, int>> nw;
nw[w] = {1, 1};
q.emplace(u, cen, w, 1);
while (!q.empty()) {
auto [qu, qp, qw, ql] = q.front();
q.pop();
for (auto &[v, ww] : adj[qu]) {
if (v == qp || rem[v] || ww + qw > K) continue;
if (!nw.count(ww+qw)) nw[ww+qw] = {ql+1, 1};
else if (nw[ww+qw].first > ql+1) nw[ww+qw] = {ql+1, 1};
else if (nw[ww+qw].first == ql+1) nw[ww+qw].second++;
q.emplace(v, qu, ww+qw, ql+1);
}
}
for (auto &[len, val] : nw) {
if (!mn.count(K-len)) continue;
int a = mn[K-len].first + val.first, b = mn[K-len].second * val.second;
if (a < ans.first) ans = {a, b};
else if (a == ans.first) ans.second += b;
}
for (auto &[len, val] : nw) {
if (!mn.count(len)) mn[len] = val;
if (mn[len].first > val.first) mn[len] = val;
else if (mn[len].first == val.first) mn[len].second += val.second;
}
}
for (auto &[u, w] : adj[cen]) {
if (rem[u]) continue;
build(u);
}
};
build(0);
if (ans.first == 1e9) return -1;
else return ans.second;
}
