#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
map<int, int> adj[200000];
int n, k;
bool did = false;
map<long long, int> dfs2(int i, int p = -1, int d = 0, long long l = 0) {
if (l > k) return {};
map<long long, int> m = {{l, d}};
for (auto [j, jl] : adj[i]) {
if (j == p) continue;
map<long long, int> rm = dfs2(j, i, d + 1, l + jl);
if (rm.size() > m.size()) swap(rm, m);
for (auto [cl, cd] : rm) {
if (m.count(cl)) m[cl] = min(m[cl], cd);
else m[cl] = cd;
}
}
return m;
}
int dfs1(int i, int s = n, int p = -1) {
int res = 1;
int ash = true;
map<int, int> sizes;
for (auto [j, l] : adj[i]) {
if (j == p) continue;
int jres = dfs1(j, s, i);
if (did) return jres;
sizes[j] = jres;
res += jres;
ash = ash && jres <= s / 2;
}
if (p != -1) ash = ash && s - res <= s / 2, sizes[p] = s - res;
if (ash) {
res = 1000000;
map<long long, int> m = {{0, 0}};
for (auto [j, l] : adj[i]) {
adj[j].erase(i);
map<long long, int> rm = dfs2(j, -1, 1, l);
if (rm.size() > m.size()) swap(rm, m);
for (auto [cl, d] : rm) {
if (m.count(k - cl)) res = min(res, d + m[k - cl]);
}
for (auto [cl, d] : rm) {
if (m.count(cl)) m[cl] = min(m[cl], d);
else m[cl] = d;
}
res = min(res, dfs1(j, sizes[j]));
did = false;
adj[j][i] = l;
}
did = true;
return res;
}
return res;
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N, k = K;
fo(i, 0, n - 1) {
adj[h[i][0]][h[i][1]] = l[i];
adj[h[i][1]][h[i][0]] = l[i];
}
int res = dfs1(0);
return res == 1000000 ? -1 : res;
}
