#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
vector<vector<pair<int, int>>> adj;
vector<int> centroid;
vector<int> sz;
int k;
int szDfs(int a, int p){
sz[a] = 1;
for (auto &[b, _] : adj[a]) {
if(b == p || centroid[b]) continue;
sz[a] += szDfs(b, a);
}
return sz[a];
}
int getCentroid(int a, int p, int curSz){
for (auto &[b, _] : adj[a]) {
if(b == p || centroid[b]) continue;
if(sz[b] * 2 > curSz) return getCentroid(b, a, curSz);
}
return a;
}
void dDfs(int a, int p, int d, int dc, vector<pair<int, int>> &dst){
dst.push_back({dc, d});
for (auto &[b, c] : adj[a]) {
if(b == p || centroid[b]) continue;
dDfs(b, a, d + 1, dc + c, dst);
}
}
int getBest(int a){
multiset<pair<int, int>> cur;
cur.insert({0, 0});
vector<vector<pair<int, int>>> ch;
int res = INT_MAX;
int ctd = getCentroid(a, a, szDfs(a, a));
centroid[ctd] = true;
for (auto [b, c] : adj[ctd]) {
if(centroid[b]) continue;
ch.push_back({});
dDfs(b, b, 1, c, ch.back());
}
for (auto &&i : ch) for (auto &&j : i){
cur.insert(j);
}
for (auto &&i : ch) {
for (auto &&j : i) cur.erase(cur.find(j));
for (auto &&j : i) {
if(cur.lower_bound({k - j.first, 0}) == cur.end()) continue;
pair<int, int> x = *cur.lower_bound({k - j.first, 0});
if(x.first == k - j.first){
res = min(res, x.second + j.second);
}
}
for (auto &&j : i) cur.insert(j);
}
for (auto &[b, _] : adj[ctd]) {
if(centroid[b]) continue;
res = min(res, getBest(b));
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
adj.assign(N, {});
sz.assign(N, 0);
centroid.assign(N, false);
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
int ret = getBest(0);
if(ret == INT_MAX) return -1;
return ret;
}
