#include "race.h"
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
// #define int long long
#define inf ((int)1e18)
using namespace std;
int ans, k;
vector <vector<pair<int, int> > > adj;
vector <map<int, int> > mp;
vector <int> depth, len;
void dfs(int node, int ata) {
if(adj[node].size() == 1 and adj[node][0].first == ata) {
mp[node].insert({0, 0});
return;
}
// cerr<<"nodeata: "<<node<<" "<<ata<<"\n";
int mx = 0, mxnode = -1, ww = -1;
for(auto &[to, w]:adj[node]) {
if(to == ata) continue;
dfs(to, node);
if((int)mp[to].size() > mx) {
mxnode = to;
mx = (int)mp[to].size();
ww = w;
}
}
mp[node].swap(mp[mxnode]);
// change to depth and valdepth
len[node] = len[mxnode] + ww;
depth[node] = depth[mxnode] + 1;
mp[node].insert({0 - len[node], 0 - depth[node]});
if(mp[node].count(k - len[node])) {
ans = min(ans, mp[node][k - len[node]] + depth[node]);
}
// cerr<<"check "<<node<<" "<<mxnode<<" "<<len[node]<<" "<<depth[node]<<":\n";
for(auto it:mp[node]) {
// cerr<<it.first<<" "<<it.second<<"\n";
}
for(auto &[to, w]:adj[node]) {
if(to == mxnode or to == ata) continue;
for(auto it:mp[to]) {
int realval = len[to] + it.first + w;
int realdepth = depth[to] + it.second + 1;
//check if k
int need = (k - realval) - len[node];
if(mp[node].count(need)) { // bu yanlışlıkla var olabilir?
ans = min(ans, (mp[node][need] + depth[node] + realdepth));
}
// add it to map
if(mp[node].count(realval - len[node]) )
mp[node].insert({realval - len[node], realdepth - depth[node]});
else
mp[node][realval - len[node]] = min(mp[node][realval - len[node]], realdepth - depth[node]);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans = inf, k = K;
adj.clear(); adj.resize(N + 5);
map <int, int> tmp;
mp.clear(); mp.assign(N + 5, tmp);
// try
depth.clear(); depth.resize(N + 5);
len.clear(); len.resize(N + 5);
for(int i = 0; i < N - 1; i++) {
int a = H[i][0], b = H[i][1], w = L[i];
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
dfs(0, -1);
return (ans == inf) ? -1 : ans;
}
// #define MAX_N 500000
// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;
// inline
// void my_assert(int e) {if (!e) abort();}
// void read_input()
// {
// int i;
// my_assert(2==scanf("%lld %lld",&N,&K));
// for(i=0; i<N-1; i++)
// my_assert(3==scanf("%lld %lld %lld",&H[i][0],&H[i][1],&L[i]));
// my_assert(1==scanf("%lld",&solution));
// }
// int32_t main()
// {
// int ans;
// read_input();
// ans = best_path(N,K,H,L);
// if(ans==solution)
// printf("Correct.\n");
// else
// printf("Incorrect. Returned %lld, Expected %lld.\n",ans,solution);
// return 0;
// }
