#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 2e5+1;
using pii = pair<int, int>;
vector<pii> adj[maxN];
int sz[maxN], dead[maxN];
int n, k;
int ans = 1e9;
map<int, int> mn;
int calc_sz(int v, int p=0) {
sz[v] = 1;
for (auto [u, _]: adj[v]) if (!dead[u] && u!=p) sz[v] += calc_sz(u, v);
return sz[v];
}
int find_cd(int v, int tree_sz, int p=0) {
for (auto [u, _]: adj[v]) if (!dead[u] && u!=p) {
if (sz[u]*2>tree_sz) return find_cd(u, tree_sz, v);
}
return v;
}
void calc_dist(int v, int p, int dist, int dep, bool insert) {
if(dist>k) return;
if (insert) {
if (mn.count(dist)) mn[dist] = min(mn[dist], dep);
else mn[dist] = dep;
} else {
if (mn.count(k-dist)) ans = min(ans, mn[k-dist]+dep);
}
for (auto [u, w]: adj[v]) if (!dead[u] && u!=p) calc_dist(u, v, dist+w, dep+1, insert);
}
void decomp(int v) {
int cd = find_cd(v, calc_sz(v));
mn[0] = 0;
for (auto [u, w]: adj[cd]) if (!dead[u]) {
calc_dist(u, cd, w, 1, false);
calc_dist(u, cd, w, 1, true);
}
mn.clear();
dead[cd] = true;
for (auto [u, _]: adj[cd]) if (!dead[u]) decomp(u);
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (int i=0; i<N-1; i++) {
int u = H[i][0]+1;
int v = H[i][1]+1;
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
decomp(1);
if (ans==1e9) return -1;
return ans;
}
