#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]);
// do depth and len
len[node] = len[mxnode] + ww;
depth[node] = depth[mxnode] + 1;
mp[node][0 - len[node]] = 0 - depth[node];
if(mp[node].count(k - len[node])) {
ans = min(ans, mp[node][k - len[node]] + depth[node]);
}
//kendi subtreesinden eklenen şeye bakabiliyor yanlışlıkla
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)) {
ans = min(ans, (mp[node][need] + depth[node] + realdepth));
}
}
for(auto it:mp[to]) {
int realval = len[to] + it.first + w;
int realdepth = depth[to] + it.second + 1;
// 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]);
}
}
}
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
ans = inf, k = K;
if(N == 1) {
return -1;
}
adj.clear(); adj.resize(N + 5);
map <int, int> tmp;
mp.clear(); mp.assign(N + 5, tmp);
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);
// for(auto &[tv, td]:mp[0]) {
// int realval = tv + len[0];
// int realdepth = td + depth[0];
// cout<<realval<<" "<<realdepth<<"\n";
// }
return (ans == inf) ? -1 : ans;
}
