#include "race.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
const int sz = 500200, inf = 1000000000;
struct CentroidDecomposition {
vector<vector<array<int, 2>>> g;
vector<int> sz;
vector<bool> removed;
vector<vector<array<int, 2>>> dis;
int n, k, ans;
CentroidDecomposition(int n, vector<vector<array<int, 2>>> &g, int k) : n(n) , g(g), k(k) {
removed.assign(n + 1, false);
sz.assign(n + 1, 0);
dis.resize(n + 1);
ans = inf;
}
int getSubsize(int u, int p = -1) {
sz[u] = 1;
for (auto &[v, w] : g[u])
if (!removed[v] && v != p) sz[u] += getSubsize(v, u);
return sz[u];
}
int findCentroid(int u, int half, int p = -1) {
for (auto &[v, w] : g[u]) {
if (v != p && !removed[v] && sz[v] > half) return findCentroid(v, half, u);
}
return u;
}
void dfs(int u, int centroid, unordered_map<int, int> &mn, int dep = 0, int weight = 0, int p = -1) {
if (weight > k) return;
if (mn.count(k - weight))
ans = min(ans, dep + mn[k - weight]);
dis[centroid].push_back({dep, weight});
for (auto &[v, w] : g[u]) {
if (removed[v] || v == p) continue;
dfs(v, centroid, mn, dep + 1, weight + w, u);
}
}
int build(int v = 1) { // TODO inside
int Subsize = getSubsize(v);
int centroid = findCentroid(v, Subsize / 2);
removed[centroid] = true;
unordered_map<int, int> mn;
mn[0] = 0;
for (auto &[u, w] : g[centroid]) {
if (removed[u]) continue;
dfs(u, centroid, mn, 1, w);
for (auto [dep, weight] : dis[centroid]) {
if (mn.count(weight))
mn[weight] = min(mn[weight], dep);
else
mn[weight] = dep;
}
dis[centroid].clear();
}
for (auto &[u, w] : g[centroid]) {
if (removed[u]) continue;
build(u);
}
return centroid;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
int n = N, k = K;
vector<vector<array<int, 2>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
H[i][0]++, H[i][1]++;
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
CentroidDecomposition c(n, g, k);
c.build();
return (c.ans == inf ? -1 : c.ans);
}
