#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int MAXN = 2e5 + 7;
vector<pii> g[MAXN];
bool blocked[MAXN];
int sz[MAXN];
int parent[MAXN];
int n, k;
ll ans;
map<ll, ll> m;
vector<pll> akt;
int dfs(int v, int p){
sz[v] = 1;
parent[v] = p;
for(auto ele : g[v]){
if(ele.fi == p || blocked[ele.fi]){
continue;
}
sz[v] += dfs(ele.fi, v);
}
return sz[v];
}
void dfs2(int v, int p, pll s){
akt.pb(s);
for(auto ele : g[v]){
if(blocked[ele.fi] || p == ele.fi){
continue;
}
dfs2(ele.fi, v, {s.fi + ele.se, s.se + 1});
}
}
void centroid_decomposition(int centroid){
int roz = dfs(centroid, centroid);
while(true){
bool f = 0;
for(auto ele : g[centroid]){
if(ele.fi == parent[centroid] || blocked[ele.fi]){
continue;
}
if(sz[ele.fi] * 2 >= roz){
centroid = ele.fi;
break;
}
}
if(!f){
break;
}
}
blocked[centroid] = 1;
m.clear();
m[0] = 0;
for(auto ele : g[centroid]){
if(blocked[ele.fi]){
continue;
}
akt.clear();
dfs2(ele.fi, ele.fi, {ele.se, 1});
for(auto ele2 : akt){
if(ele2.fi == k){
ans = min(ans, ele2.se);
}else if(ele2.fi < k){
if(m[k - ele2.fi] != 0){
ans = min(ans, ele2.se + m[k - ele2.fi]);
}
}
}
for(auto ele2 : akt){
if(m[ele2.fi] == 0){
m[ele2.fi] = ele2.se;
}else{
m[ele2.fi] = min(m[ele2.fi], ele2.se);
}
}
}
for(auto ele : g[centroid]){
if(blocked[ele.fi]){
continue;
}
centroid_decomposition(ele.fi);
}
}
int best_path(int N, int K, int H[][2], int L[]){
ans = 1e9;
n = N;
k = K;
//cout << n << ' ' << k << '\n';
for(int i = 0; i < n - 1; i++){
//cout << H[i][0] << ' ' << H[i][1] << ' ' << L[i] << '\n';
g[H[i][0]].pb({H[i][1], L[i]});
g[H[i][1]].pb({H[i][0], L[i]});
}
centroid_decomposition(0);
if(ans == (ll)1e9){
return -1;
}
return (int)ans;
}
/*int main(){
int tab[3][2] = {{0, 1}, {1, 2}, {1, 3}};
int l[3] = {1, 2, 4};
cout << best_path(4, 3, tab, l) << '\n';
return 0;
}*/
