#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int INF = (int)1e9;
struct MinMaxMerge {
map<int, int> dist;
int lazy_weight, lazy_edges;
MinMaxMerge() : lazy_weight(0), lazy_edges(0) {
dist.clear();
}
};
struct Solver {
Solver(int k_, const vector<vector<pair<int, int>>> &adj_) :
n(adj_.size()), k(k_), adj(adj_) {}
int n, k, ans = INF;
vector<vector<pair<int, int>>> adj;
void Merge(MinMaxMerge &curr, MinMaxMerge &him) {
if (curr.dist.size() < him.dist.size()) {
swap(curr, him);
}
for (auto &p : him.dist) {
int real_weight = p.first + him.lazy_weight;
int real_edges = p.second + him.lazy_edges;
int search = k - real_weight - curr.lazy_weight;
if (curr.dist.count(search)) {
ans = min(ans, curr.dist[search] + curr.lazy_edges + real_edges);
}
}
for (auto &p : him.dist) {
int dist = p.first + him.lazy_weight - curr.lazy_weight;
int edges = p.second + him.lazy_edges - curr.lazy_edges;
if (curr.dist.count(dist)) {
curr.dist[dist] = min(curr.dist[dist], edges);
} else {
curr.dist[dist] = edges;
}
}
}
MinMaxMerge DFS(int node, int parent) {
MinMaxMerge curr;
curr.dist[0] = 0;
for (auto &p : adj[node]) if (p.first != parent) {
auto him = DFS(p.first, node);
him.lazy_weight += p.second;
++him.lazy_edges;
Merge(curr, him);
}
return curr;
}
int Solve() {
DFS(0, -1);
return ans == INF ? -1 : ans;
}
};
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]);
}
Solver solver(k, adj);
return solver.Solve();
}
