#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
#define ce cout<<endl;
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using T = pair<ll,int>;
const ll INF = 1e18;
const int N = 2e5;
const int MAXM = 4200005;
const int LOG2 = 17;
const int inv = 1112;
const int MOD =998244353 ;
int dx[]= {0,0,-1,1};
int dy[] = {1 , - 1 , 0 , 0};
// Author : T_Danh - Tri An High School
vector<pii> adj[N + 1];
int res = 1e9;
ll prefix[N + 1] ;
int h[N + 1];
void pre_cal(int u , int p){
for(auto& [v , w] : adj[u]) if(v != p){
prefix[v] = prefix[u] + w;
h[v] = h[u] + 1;
pre_cal(v , u);
}
}
unordered_map<ll,int> dfs(int u, int p, int k ) {
unordered_map<ll,int> cur;
cur[prefix[u]] = h[u];
for(auto& [v , w] : adj[u]) if(v != p){
unordered_map<ll,int> tmp = dfs(v , u, k);
if(cur.size() < tmp.size()) swap(cur , tmp);
for(auto& [val , d] : tmp){
ll target = (ll)k + 2LL * prefix[u] - val;
if(cur.count(target)){
res = min(res, d + cur[target] - 2 * h[u]);
}
}
for(auto& [val , d] : tmp){
if(cur.find(val) == cur.end() || d < cur[val]){
cur[val] = d;
}
}
}
return cur;
}
int best_path(int n, int k, int H[][2], int L[]) {
// --- BẮT BUỘC PHẢI RESET DỮ LIỆU ---
res = 1e9;
for(int i = 0; i < n; i++) {
adj[i].clear();
prefix[i] = 0;
h[i] = 0;
}
// -----------------------------------
FOR(i,0,n-1){
adj[H[i][0]].eb(H[i][1] , L[i]);
adj[H[i][1]].eb(H[i][0] , L[i]);
}
pre_cal(0, -1);
dfs(0, -1, k);
if(res == 1e9) return -1;
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// #define NAME "runaway"
// if (fopen(NAME ".in", "r"))
// freopen(NAME ".in", "r", stdin),
// freopen(NAME ".out", "w", stdout);
// solve();
// return 0;
// }
