#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200'000;
int n, k;
int ans = INT_MAX;
struct state {
int delta_k = 0;
int delta_v = 0;
map<int, int> min_n;
state() {
min_n[0] = 0;
}
void incr(int d) {
delta_k += d;
++delta_v;
auto it = min_n.find(k - delta_k);
if (it != min_n.end()) ans = min(ans, it->second + delta_v);
min_n.erase(min_n.upper_bound(k - delta_k), min_n.end());
}
void merge(state other) {
if (min_n.size() < other.min_n.size()) {
swap(delta_k, other.delta_k);
swap(delta_v, other.delta_v);
swap(min_n, other.min_n);
}
for (pair<int, int> const& p : other.min_n) {
int key, val;
tie(key, val) = p;
key += other.delta_k;
val += other.delta_v;
int rem = k - key;
auto it = min_n.find(rem - delta_k);
if (it != min_n.end()) {
ans = min(ans, val + it->second + delta_v);
}
}
for (pair<int, int> const& p : other.min_n) {
int key, val;
tie(key, val) = p;
key += other.delta_k;
val += other.delta_v;
auto it = min_n.find(key - delta_k);
if (it == min_n.end()) {
it = min_n.insert({key - delta_k, val - delta_v}).first;
} else if (val < it->second + delta_v) {
it->second = val - delta_v;
}
}
}
};
vector<int> g[MAX_N];
int parent[MAX_N];
int len[MAX_N];
void dfs1(int u) {
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfs1(v);
}
}
state dfs2(int u) {
state st;
for (int v : g[u]) {
if (parent[v] == u) st.merge(dfs2(v));
}
st.incr(len[u]);
return st;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i < n - 1; ++i) {
g[H[i][0]].push_back(H[i][1]);
g[H[i][1]].push_back(H[i][0]);
}
dfs1(0);
for (int i = 0; i < n - 1; ++i) {
if (parent[H[i][1]] == H[i][0]) swap(H[i][0], H[i][1]);
len[H[i][0]] = L[i];
}
dfs2(0);
return ans == INT_MAX ? -1 : ans;
}
