#include "race.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int nax = 2e5 + 5;
vector<pair<int, int>> adj[nax];
int k;
struct Centroid {
vector<int> sz;
vector<bool> vis;
int ans = INT_MAX;
void init(int n) {
sz.resize(n);
vis.assign(n, false);
}
int find_size(int v, int p=-1) {
if (vis[v]) {
return 0;
}
sz[v] = 1;
for(auto u : adj[v]) {
if (u.first == p) continue;
sz[v] += find_size(u.first, v);
}
return sz[v];
}
int find_centroid(int v, int p, int n) {
for(auto u : adj[v]) {
if (u.first == p || vis[u.first]) continue;
if (sz[u.first] > n/2) {
return find_centroid(u.first, v, n);
}
}
return v;
}
map<int, int> mp;
void dfs(int v, int p, int depth, int cost, bool filling) {
if (cost > k) return;
if (cost == k) {
ans = min(ans, depth);
return;
}
if (filling) {
if (mp.find(cost) == mp.end() || mp[cost] > depth) {
mp[cost] = depth;
}
}
else {
if (mp.find(k-cost) != mp.end()) {
ans = min(ans, depth + mp[k-cost]);
// cerr << "in: " << depth + mp[k-cost] << "\n";
}
}
for(auto u : adj[v]) {
if (u.first == p || vis[u.first]) continue;
dfs(u.first, v, depth+1, cost+u.second, filling);
}
}
void sol(int v) {
mp.clear();
for(auto u : adj[v]) {
if (vis[u.first]) continue;
// cout << v << "->" << u.first << " cost " << u.second << "\n";
dfs(u.first, v, 1, u.second, false);
dfs(u.first, v, 1, u.second, true);
}
}
void init_centroid(int v=0, int p=-1) {
find_size(v);
int c = find_centroid(v, p, sz[v]);
vis[c] = true;
sol(c);
// cout << c << " " << ans << "\n";
for(auto u : adj[c]) {
if (!vis[u.first]) {
init_centroid(u.first, c);
}
}
}
};
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
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]});
}
Centroid ct;
ct.init(N+6);
ct.init_centroid();
return ct.ans == INT_MAX ? -1 : ct.ans;
}
