#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
class MAP {
unordered_map<ll, ll> mp;
ll a = 0, b = 0;
public:
ll get(ll key) {
if (!mp.contains(key-a)) {
return -1;
}
return mp[key-a]+b;
}
void increase(ll x) {
a += x;
b++;
}
void insert(ll key, ll val) {
key -= a;
val -= b;
if (!mp.contains(key)) {
mp[key] = val;
}
else {
mp[key] = min(mp[key], val);
}
}
vector<pair<ll, ll>> clear() {
vector<pair<ll, ll>> v;
for (auto i : mp) {
v.push_back({i.first+a, i.second+b});
}
mp = unordered_map<ll, ll>();
a = 0;
b = 0;
return v;
}
int size() {
return (int)mp.size();
}
};
void dfs (int v, vector<vector<pair<ll, ll>>> &g, vector<bool> &odw, vector<MAP> &mp, vector<int> &wsk, ll &w, int k) {
//cout << v << '\n';
odw[v] = 1;
vector<pair<int, int>> x;
for (auto u : g[v]) {
if (!odw[u.first]) {
dfs(u.first, g ,odw, mp, wsk, w, k);
mp[wsk[u.first]].increase(u.second);
x.push_back({mp[wsk[u.first]].size(), wsk[u.first]});
//cout << "wsk " << u.first << ' ' << wsk[u.first] << '\n';
}
}
if (x.empty()) {
wsk[v] = mp.size();
mp.push_back(MAP());
mp[wsk[v]].insert(0, 0);
return;
}
sort(x.begin(), x.end(), greater<pair<int, int>>());
wsk[v] = x[0].second;
mp[wsk[v]].insert(0, 0);
ll q = mp[wsk[v]].get(k);
if (q != -1) {
//cout << v << ' ' << q << '\n';
w = min(w, q);
}
for (int i = 1; i < (int)x.size(); i++) {
vector<pair<ll, ll>> p = mp[x[i].second].clear();
//cout << "i " << x[i].second << '\n';
for (auto j : p) {
//cout << j.first << ' ' << j.second << '\n';
ll a = mp[wsk[v]].get(k-j.first);
if (a != -1) {
w = min(w, a+j.second);
}
}
for (auto j : p) {
mp[wsk[v]].insert(j.first, j.second);
}
}
}
int best_path(int n, int k, int H[][2], int L[])
{
vector<vector<pair<ll, ll>>> g (n);
for (int i = 0; i < n-1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
vector<bool> odw (n, 0);
vector<MAP> mp;
vector<int> wsk (n, 0);
ll w = 1e9;
dfs(0, g, odw, mp, wsk, w, k);
if (w == (ll)1e9) {
return -1;
}
return (int)w;
}
