#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, K;
set<ll> adj[200001];
map<ll, ll> costs[200001];
ll subtree[200001], first_centroid;
ll A[1000001], component = 0, ans = 200001;
ll achievable[1000001], min_paths[1000001];
void get_subtree_sizes(ll node, ll parent) {
subtree[node] = 1;
for (ll i : adj[node])
if (i != parent) {
get_subtree_sizes(i, node);
subtree[node] += subtree[i];
}
}
ll get_centroid(ll node, ll parent, ll tree_size) {
for (ll i : adj[node])
if (i != parent && subtree[i] > tree_size)
return get_centroid(i, node, tree_size);
return node;
}
void dfs(ll node, ll parent, ll cost, ll depth, bool filling) {
if (cost > K) return;
if (filling) {
if (achievable[K - cost] == component)
ans = min(ans, depth + min_paths[K - cost]);
if (cost == K) ans = min(ans, depth);
} else {
if (achievable[cost] < component || depth < min_paths[cost]) {
achievable[cost] = component;
min_paths[cost] = depth;
}
}
for (ll i : adj[node])
if (i != parent)
dfs(i, node, cost + costs[node][i], depth + 1, filling);
}
void process(ll node) {
get_subtree_sizes(node, 0);
ll centroid = get_centroid(node, 0, subtree[node] / 2);
component++;
for (ll i : adj[centroid]) {
dfs(i, centroid, costs[centroid][i], 1, 1);
dfs(i, centroid, costs[centroid][i], 1, 0);
}
for (ll i : adj[centroid]) {
adj[i].erase(centroid);
adj[centroid].erase(i);
process(i);
}
}
int best_path(int n_, int k_, int edges[][2], int weights[]) {
if (k_ == 1){
return 0;
}
N = n_;
K = k_;
ans = 200001;
for (int i = 0; i < N - 1; i++) {
int u = edges[i][0];
int v = edges[i][1];
adj[u].insert(v);
adj[v].insert(u);
costs[u][v] = costs[v][u] = weights[i];
}
process(1);
return (ans == 200001 ? -1 : ans);
}
