#include <bits/stdc++.h>
#include "race.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
const int N = (int)2e5 + 5;
int K, ans;
vector<int> D, sz;
vector<ll> S;
vector<map<ll, int>*> m;
vector<vector<pair<int, int>>> E;
int dfs_sz(int x, int p = -1) {
for (auto [i, w] : E[x]) {
if (i != p) {
D[i] = D[x] + 1;
S[i] += S[x] + w;
sz[x] += dfs_sz(i, x);
}
}
return sz[x];
}
void dfs(int x, int p = -1) {
int y = -1;
for (auto [i, w] : E[x]) {
if (i != p && (!~y || sz[y] < sz[i])) y = i;
}
if (~y) {
dfs(y, x);
m[x] = m[y];
}
else m[x] = new map<ll, int> ();
(*m[x])[S[x]] = D[x];
for (auto [i, w] : E[x]) {
if (i != p && i != y) {
dfs(i, x);
for (auto [j, d] : *m[i]) {
ll a = K + 2 * S[x] - j;
if (m[x]->find(a) != m[x]->end()) ans = min(ans, (*m[x])[a] + d - 2 * D[x]);
}
for (auto [j, d] : *m[i]) {
if (m[x]->find(j) == m[x]->end()) (*m[x])[j] = d;
else (*m[x])[j] = min((*m[x])[j], d);
}
}
}
if (m[x]->find(K + S[x]) != m[x]->end()) ans = min(ans, (*m[x])[K + S[x]] - D[x]);
}
int best_path(int n, int k, int H[][2], int L[]) {
K = k;
E.assign(n, {});
for (int i = 0; i < n - 1; i++) {
E[H[i][0]].push_back({H[i][1], L[i]});
E[H[i][1]].push_back({H[i][0], L[i]});
}
D.assign(n, 0);
S.assign(n, 0);
sz.assign(n, 1);
dfs_sz(0);
ans = n;
m.assign(n, {});
dfs(0);
return (ans == n ? -1 : ans);
}
