#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int ans = INT_MAX;
vector<vector<pair<int, int>>> adj;
vector<int> best, ct, subtree_size, centroids;
int considere = 0;
int k;
// dfs1: consulta complementos procurando pares que somem K
void dfs1(int u, int p, int edges, int w)
{
if (w > k) return;
if (centroids[u]) return;
int goal = k - w;
int value = INT_MAX;
if (goal >= 0 && goal <= k && ct[goal] == considere)
value = best[goal];
if (value != INT_MAX)
ans = min(ans, value + edges);
for (auto &pr : adj[u]) {
int v = pr.first;
int weight = pr.second;
if (v == p) continue;
if (centroids[v]) continue;
dfs1(v, u, edges + 1, w + weight);
}
}
// dfs2: atualiza "best" com as distâncias desta subárvore
void dfs2(int at, int prev, int edges, int w)
{
if (w > k) return;
if (centroids[at]) return;
if (w >= 0 && w <= k) {
if (ct[w] == considere) best[w] = min(best[w], edges);
else { best[w] = edges; ct[w] = considere; }
}
for (auto &pr : adj[at]) {
int to = pr.first;
int weight = pr.second;
if (to == prev) continue;
if (centroids[to]) continue;
dfs2(to, at, edges + 1, weight + w);
}
}
void subtree_sz(int at, int prev)
{
subtree_size[at] = 1;
for (auto &pr : adj[at]) {
int to = pr.first;
int w = pr.second;
if (to == prev) continue;
if (centroids[to]) continue;
subtree_sz(to, at);
subtree_size[at] += subtree_size[to];
}
}
int find_centroid(int at, int prev, int n)
{
for (auto &pr : adj[at]) {
int to = pr.first;
int w = pr.second;
if (to == prev || centroids[to]) continue;
if (subtree_size[to] > n / 2)
return find_centroid(to, at, n);
}
return at;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
adj.assign(N, {});
best.assign(K + 1, INF);
ct.assign(K + 1, -1);
subtree_size.assign(N, 0);
centroids.assign(N, 0);
considere = 0;
ans = INF;
for (int i = 0; i < N - 1; i++) {
int a = H[i][0], b = H[i][1], w = L[i];
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
queue<int> q;
q.push(0);
while (!q.empty()) {
int at = q.front(); q.pop();
if (centroids[at]) continue;
subtree_sz(at, -1);
int centroid = find_centroid(at, -1, subtree_size[at]);
best[0] = 0;
ct[0] = considere;
centroids[centroid] = 1;
for (auto &pr : adj[centroid]) {
int to = pr.first;
int w = pr.second;
if (!centroids[to]) {
dfs1(to, centroid, 1, w);
dfs2(to, centroid, 1, w);
q.push(to);
}
}
considere++;
}
return (ans == INF) ? -1 : ans;
}
