#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define V vector
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
struct edge {int v, l;};
int N, K;
V<V<edge>> adj;
V<bool> used;
int centroid(int u, int par, int &root, int size){
//if(u == par) cout << "calling centroid " << u << " " << size << endl;
int sz = 1;
int ma = 0;
for(edge e : adj[u]) if(!used[e.v] and e.v != par) {
int s = centroid(e.v, u, root, size);
sz += s;
ma = max(ma, s);
}
//if(size != 0)
// cout << "largest " << max(ma, size-sz) << endl;
if(max(ma, size-sz) <= size/2) root = u;
//if(size != 0) cout << u << " " << par << " " << sz << endl;
return sz;
}
void dfs(int u, int par, int d, int l, vii &paths){
//cout << "dfs " << u << " " << par << endl;
paths.pb({d, l});
for(edge e : adj[u]) if(!used[e.v] and e.v != par) dfs(e.v, u, d+e.l, l+1, paths);
}
int shortest(int u){
//cout << "shortest " << u << endl;
int root, sz;
sz = centroid(u, u, root, 0);
centroid(u, u, root, sz);
//cout << "root " << root << " " << sz << endl;
used[root] = 1;
map<int, int> paths;
int best = 1e9;
for(edge e : adj[root]) if(!used[e.v]) {
vii pa;
dfs(e.v, root, e.l, 1, pa);
for(ii p : pa){
int &l = paths[ K - p.fst ];
if(l != 0) best = min(best, p.snd + l);
if(p.fst == K) best = min(best, p.snd);
}
for(ii p : pa){
int &l = paths[p.fst];
if(l == 0) l = p.snd;
else l = min(l, p.snd);
}
}
for(edge e : adj[root]) if(!used[e.v]) best = min(best, shortest(e.v));
return best;
}
INT best_path(INT n, INT k, INT H[][2], INT L[]) {
N = n; K = k;
adj.resize(N);
used.assign(N, 0);
FOR(i, 0, N-1) {
//if(L[i] + L[i+1] == K) {cerr << i << endl; return 2;}
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
int res = shortest(0);
return res == 1e9 ? -1 : res;
}
