#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
#define uniq(x) unique(all(x)), x.end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
struct Graph {
int n, k;
int tot = 2e9;
map <int, int> H;
vt <ar <int, 2>> paths;
vt <vt <ar <int, 2>>> adj;
Graph(int n, int k): n(n), k(k) {
H.clear();
paths.clear();
adj.assign(n, vt <ar <int, 2>>());
}
void add_edge(int u, int v, int w) {
adj[u].pub({v, w});
adj[v].pub({u, w});
}
void dfs(int u, int p, int c, int lvl = 1) {
if (c > k) {
return;
}
paths.pub({c, lvl});
for (auto& [v, w] : adj[u]) {
if (v == p || rem[v])
continue;
dfs(v, u, c + w, lvl + 1);
}
}
//Centroid Decomposition
vt <bool> rem;
vt <int> par, sz;
void initCD() {
sz.resize(n);
rem.resize(n);
par.resize(n);
build(0, -1);
}
void build(int u, int p) {
int n = dfsC(u, p);
int centroid = get_centroid(u, p, n);
par[centroid] = p;
rem[centroid] = true;
H.clear();
H[0] = 0;
for (auto& [v, w] : adj[centroid]) {
if (rem[v]) {
continue;
}
paths.clear();
dfs(v, centroid, w);
for (auto& [path, nr] : paths) {
if (H.count(k - path))
tot = min(tot, H[k - path] + nr);
}
for (auto& [path, nr] : paths) {
if (H.count(path)) H[path] = min(H[path], nr);
else H[path] = nr;
}
}
for (auto& [v, w] : adj[centroid]) {
if (rem[v]) {
continue;
}
build(v, centroid);
}
}
int dfsC(int u, int p) {
sz[u] = 1;
for (auto& [v, w] : adj[u]) {
if (v == p || rem[v])
continue;
dfsC(v, u);
sz[u] += sz[v];
}
return sz[u];
}
int get_centroid(int u, int p, int n) {
for (auto& [v, w] : adj[u]) {
if (v == p || rem[v])
continue;
if (sz[v] * 2 > n)
return get_centroid(v, u, n);
}
return u;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
Graph G(N, K);
for (int i = 0; i < N - 1; ++i) {
G.add_edge(H[i][0], H[i][1], L[i]);
}
G.initCD();
return G.tot == 2e9? -1 : G.tot;
}
