#include "race.h"
#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
struct E {
int t;
int w;
};
vector<E> al[200000];
int sts[200000];
bool block[200000];
int n, k;
void calc_sts(int v, int p) {
if(block[v]) {
sts[v] = 0;
return;
}
sts[v] = 1;
for(auto a : al[v]) {
if(a.t == p) continue;
calc_sts(a.t, v);
sts[v] += sts[a.t];
}
}
int centr_walk(int v) {
for(auto a : al[v]) {
if(2*sts[a.t] > sts[v]) {
sts[v] -= sts[a.t];
sts[a.t] += sts[v];
return centr_walk(a.t);
}
}
return v;
}
struct P {
ll v;
int l;
friend bool operator < (const P& a, const P& b) {
return (a.v < b.v) || (a.v == b.v && a.l < b.l);
}
};
void paths_dfs(vector<P>& ps, int v, int p, ll d, int l) {
if(block[v]) return;
ps.push_back({d, l});
for(auto a : al[v]) {
if(a.t == p) continue;
paths_dfs(ps, a.t, v, d+a.w, l+1);
}
}
int decomp(int v) {
if(block[v]) return 2000000;
calc_sts(v, v);
v = centr_walk(v);
set<P> pst;
pst.insert({0, 0});
int best = 2000000;
for(auto a : al[v]) {
if(block[a.t]) continue;
vector<P> ps;
paths_dfs(ps, a.t, v, a.w, 1);
for(auto p : ps) {
auto lb = pst.lower_bound({k-p.v, 0});
if(lb == pst.end()) continue;
if(lb->v + p.v != k) continue;
D(lb->v)
D(lb->l)
D(p.v)
D(p.l)
best = min(best, lb->l+p.l);
}
for(auto p : ps) {
pst.insert(p);
}
}
block[v] = true;
for(auto a : al[v]) {
best = min(best, decomp(a.t));
}
return best;
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N; k = K;
for(int i = 0; i < n-1; ++i) {
al[h[i][0]].push_back({h[i][1], l[i]});
al[h[i][1]].push_back({h[i][0], l[i]});
}
int r = decomp(0);
if(r >= 2000000) return -1;
return r;
}
