#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pll pair <ll, ll>
const ll N = 3 * 1e5 + 100, M = 1e6 + 100;
vector <pll> q[N];
int k, ans = INT_MAX;
bool was[N];
int need[M], cnt[N];
void dfs(int v, int pred){
cnt[v] = 1;
for(auto u : q[v]){
if(u.F == pred) continue;
dfs(u.F, v);
cnt[v] += cnt[u.F];
}
}
int get(int v, int p){
for(auto u : q[v]){
if(u.F == p || was[u.F]) continue;
if(cnt[u.F] * 2 >= cnt[v]){
cnt[v] -= cnt[u.F];
cnt[u.F] += cnt[v];
return get(u.F, v);
}
}
return v;
}
vector <int >vec;
void obs(int v, int pred, int sum, int ct, int code){
//cout <<v << " ";
if(sum == k) ans = min(ans, ct);
if(sum < k){
if(code == 0){
if(need[k - sum] != 0) ans = min(ans, ct + need[k - sum]);
} else{
if(need[sum] == 0) need[sum] = ct;
else need[sum] = min(need[sum], ct);
vec.pb(sum);
}
}
for(auto u : q[v]){
if(was[u.F] || pred == u.F) continue;
obs(u.F, v, sum + u.S, ct + 1, code);
}
}
void centroid(int v){
v = get(v, -1);
was[v] = true;
//cout << v << " Centroid\n";
for(auto u : q[v]){
if(was[u.F]) continue;
obs(u.F, -1, u.S, 1, 0);
obs(u.F, -1, u.S, 1, 1);
//cout << endl;
}
for(auto u : vec){
need[u] = 0;
}
vec.clear();
for(auto u : q[v]){
if(was[u.F]) continue;
centroid(u.F);
}
}
int best_path(int n, int gk, int h[][2], int l[]){
k = gk;
for(int i = 0; i < n - 1; i++){
q[h[i][0]].pb({h[i][1], l[i]});
q[h[i][1]].pb({h[i][0], l[i]});
}
dfs(0, -1);
centroid(0);
if(ans == INT_MAX) return -1;
return ans;
}
// int main(){
// int n, gk;
// cin >> n >> gk;
// int h[n][2], l[n];
// for(int i = 0, a, b; i < n - 1; i++){
// cin >> a >> b;
// h[i][0] = a;
// h[i][1] = b;
// }
// for(int i = 0, x; i < n - 1; i++){
// cin >> x;
// l[i] = x;
// }
// cout << best_path(n, gk, h, l);
// return 0;
// }
