#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 int maxn=400000;
map<int, char> ans;
set<int> adj[maxn];
map<pll, ll> cost;
#define fs first
#define sc second
const bool DEBUG=0;
ll dist[maxn];
ll depth[maxn];
int sz[maxn];
ll K;
ll best=1e9;
int dfs(int u, int 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(int u, int 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)]);
}
}
int centroid(int u, int p, int N){
for(auto e : adj[u]){
if(e==p)continue;
if(sz[e]*2 > N) return centroid(e, u, N);
}
return u;
}
void decompose(char let, int v){
dfs(v, v);
int c = centroid(v, v, sz[v]);
ans[c]=let;
if(sz[v]==1) return;
//Prestej poti
vector<int> rem(adj[c].begin(), adj[c].end());
pre.clear();
if(DEBUG) printf("Decomposing on %d\n", c);
for(auto e : rem){
depth[c]=0;
dfs2(e, c, cost[mp(c, e)]);
if(DEBUG)printf("child %d\n", e);
for(auto p : cur){
if(DEBUG)printf("path %d %d\n", p.fs, p.sc);
auto b = *pre.lower_bound(mp(K-p.fs, 0));
if(b.fs+p.fs==K) 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(let+1, e);
}
}
int best_path(int N, int _K, int H[][2], int L[]){
FOR(i, 0, N-2){
int 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, 0);
if(best==1e9)return -1;
return best;
}
