#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 2e5+1, oo = 1e9;
static int ans,k;
struct paths {
map<ll,int> m;
ll delta=0;
int extraedge=0;
int get(ll l) {
ll tmp = l-delta;
auto iter = m.find(tmp);
if(iter!=m.end()) {
return iter->second+extraedge;
}
return oo;
}
void insert(ll l, int i) {
ll tmp = l-delta;
auto iter = m.find(tmp);
if(iter!=m.end()) {
iter->second = min(i,iter->second);
} else {
m[tmp] = i;
}
}
};
void merge(paths& a, paths& b) {
if(a.m.size()<b.m.size()) {
swap(a,b);
}
for(auto& p: b.m) {
int real = p.first+b.delta;
ans = min(ans,p.second+b.extraedge+a.get(k-real));
}
for(auto& p: b.m) {
auto real = p.first+b.delta;
a.insert(real,p.second+b.extraedge);
}
}
vector<pi> adj[mxN];
void dfs(int at, int from, int ww, paths& parent) {
paths p;
p.insert(0,0);
for(auto [to,w]: adj[at]) {
if(to==from) continue;
dfs(to,at,w,p);
}
p.delta+=ww;
p.extraedge++;
merge(parent,p);
}
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
k=K;
ans = oo;
for(int i=0;i<n;++i) adj[i].clear();
for(int i=0;i<n-1;++i) {
int a = H[i][0], b = H[i][1];
int w = L[i];
adj[a].emplace_back(b,w);
adj[b].emplace_back(a,w);
}
paths empty;
dfs(0,-1,0,empty);
return ans==oo?-1:ans;
}
