#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define loop(i, a) FOR(i, 0, a-1)
typedef long long ll;
#define pll pair<ll, ll>
const ll maxn=300000;
set<ll> adj[maxn];
map<pll, ll> cost;
#define fs first
#define sc second
const bool DEBUG=0;
ll dist[maxn];
ll depth[maxn];
ll sz[maxn];
ll K;
ll best=1e9;
int dfs(ll u, ll p){
sz[u]=1;
for(auto e:adj[u]){
if(e==p)continue;
sz[u]+=dfs(e, u);
}
return sz[u];
}
set<pll> pre;
vector<pll> cur;
void dfs2(ll u, ll p, ll d){
dist[u]=d;
depth[u]=depth[p]+1;
if(d==K) best=min(best, depth[u]);
cur.pb(mp(d, depth[u]));
for(auto e:adj[u]){
if(e==p) continue;
dfs2(e, u, d+cost[mp(u, e)]);
}
}
ll centroid(ll u, ll p, ll N){
for(auto e : adj[u]){
if(e==p)continue;
if(sz[e]*2 > N) return centroid(e, u, N);
}
return u;
}
void decompose(ll v){
dfs(v, v);
ll c = centroid(v, v, sz[v]);
if(sz[v]==1) return;
//Prestej poti
vector<ll> rem(adj[c].begin(), adj[c].end());
pre.clear();
if(DEBUG) printf("Decomposing on %lld\n", c);
for(auto e : rem){
depth[c]=0;
dfs2(e, c, cost[mp(c, e)]);
if(DEBUG)printf("child %lld\n", e);
for(auto p : cur){
if(p.fs>K) continue;
if(DEBUG)printf("path %lld %lld\n", p.fs, p.sc);
auto b_p = pre.lower_bound(mp(K-p.fs, 0));
if(b_p==pre.end()) continue;
auto b = *b_p;
if(b.fs+p.fs==K) {
if(p.sc+b.sc<best){
//printf("centroid %d found %d+%d | %d - %d\n", c, p.fs, b.fs, p.sc, b.sc);
best=min(best, p.sc+b.sc);
}
}
}
for(auto _e : cur)pre.insert(_e);
cur.clear();
}
//Rekurzivno razstavi
for(auto e : rem){
adj[c].erase(e);adj[e].erase(c);
decompose(e);
}
}
int best_path(int N, int _K, int H[][2], int L[]){
FOR(i, 0, N-2){
ll a=H[i][0], b=H[i][1];
adj[a].insert(b);adj[b].insert(a);
cost[mp(a,b)]=L[i];cost[mp(b, a)]=L[i];
}
K=_K;
decompose(0);
if(best==1e9)return -1;
return best;
}
