#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vipi;
bool cmp(tuple<int, int, int> a, tuple<int, int, int> b)
{
return get<1>(a) < get<2>(b);
}
vpi transverse(int i, int p, int& m_l, int k, vipi& g)
{
set<int> p_s;
map<int, vector<tuple<int, int, int>>> res;
for (auto ot : g[i]) {
if (ot.F == p)
continue;
vpi ret = transverse(get<0>(ot), i, m_l, k, g);
if (ot.S > k)
continue;
p_s.insert(ot.S);
res[ot.S].push_back({ ot.S, 1, ot.F });
for (auto pa : ret) {
if (pa.F + ot.S > k)
continue;
if (pa.F == 0)
continue;
p_s.insert(pa.F + ot.S);
res[pa.F + ot.S].push_back({ pa.F + ot.S, pa.S + 1, ot.F });
}
}
if (p_s.count(k)) {
m_l = min(m_l, get<1>(res[k][0]));
}
vi v;
for (int x : p_s)
v.push_back(x);
int a = 0, b = v.size() - 1;
vpi pairs;
while (a <= b) {
if (v[a] + v[b] == k) {
pairs.push_back({ v[a], v[b] });
a++;
} else if (v[a] + v[b] < k) {
a++;
} else {
b--;
}
}
for (int x : p_s)
sort(res[x].begin(), res[x].end(), cmp);
for (auto pa : pairs) {
int c = get<1>(res[pa.F][0]) + get<1>(res[pa.S][0]);
if (get<2>(res[pa.F][0]) == get<2>(res[pa.S][0])) {
//cout << "HERE" << endl;
if (res[pa.F].size() == 1 && res[pa.S].size() == 1)
continue;
else if (res[pa.S].size() == 1) {
c = c - get<1>(res[pa.F][0]) + get<1>(res[pa.F][1]);
} else if (res[pa.F].size() == 1) {
c = c - get<1>(res[pa.S][0]) + get<1>(res[pa.S][1]);
} else {
int c1 = c - get<1>(res[pa.F][0]) + get<1>(res[pa.F][1]);
int c2 = c - get<1>(res[pa.S][0]) + get<1>(res[pa.S][1]);
c = min(c1, c2);
}
}
//cout << pa.F << ' ' << pa.S << " - " << c << endl;
m_l = min(m_l, c);
}
vpi cmp(v.size());
for (int i = 0; i < v.size(); i++) {
cmp[i] = { get<0>(res[v[i]][0]), get<1>(res[v[i]][0]) };
//cout << cmp[i].F << " - " << cmp[i].S << ", ";
}
//cout << endl;
//cout << i << ' ' << m_l << endl;
return cmp;
}
signed best_path(signed N, signed K, signed H[][2], signed L[])
{
int n = N;
int k = K;
vipi g(n);
for (int i = 0; i < n - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
g[u].push_back({ v, w });
g[v].push_back({ u, w });
}
int m_l = LLONG_MAX;
transverse(0, -1, m_l, k, g);
if (m_l == LLONG_MAX)
return -1;
return (signed)m_l;
}
