#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
vector <pair <int, int> > adj[200005];
map <int, int> global_path, local_path;
bool isCentroid[200005] = {false};
int subtr_size[200005], localCentroid, k, ans;
void SubTreeSize(int v, int p) {
subtr_size[v] = 1;
for(auto &it: adj[v])
if(it.F != p && !isCentroid[it.F]) {
SubTreeSize(it.F, v);
subtr_size[v] += subtr_size[it.F];
}
return;
}
void traverse(int v, int p, int w, int l) {
if(w > k) return;
if(w == k) ans = min(ans, l);
int temp = global_path[k - w];
if(temp) ans = min(ans, l + temp);
if(!local_path[w] || local_path[w] > l) local_path[w] = l;
for(auto &it: adj[v])
if(it.F != p && !isCentroid[it.F])
traverse(it.F, v, w + it.S, l + 1);
return;
}
void findCentroid(int v, int p, int size) {
bool flag = (size - subtr_size[v] <= size / 2);
for(auto &it: adj[v])
if(it.F != p && !isCentroid[it.F]) {
flag &= (subtr_size[it.F] <= size / 2);
findCentroid(it.F, v, size);
}
if(flag) localCentroid = v;
return;
}
void go(int v) {
SubTreeSize(v, -1);
findCentroid(v, -1, subtr_size[v]);
global_path.clear();
isCentroid[localCentroid] = true;
for(auto &it: adj[localCentroid])
if(!isCentroid[it.F]) {
local_path.clear();
traverse(it.F, localCentroid, it.S, 1);
for(auto &localit: local_path)
if(!global_path[localit.F] || global_path[localit.F] > localit.S)
global_path[localit.F] = localit.S;
}
for(auto &it: adj[localCentroid])
if(!isCentroid[it.F])
go(it.F);
return;
}
int best_path(int N, int K, int H[][2], int L[]) {
int i;
k = K;
for(i = 0; i < N - 1; i++) {
adj[H[i][0]].pb(mp(H[i][1], L[i]));
adj[H[i][1]].pb(mp(H[i][0], L[i]));
}
ans = 1e9;
go(0);
if(ans == 1e9) ans = -1;
return ans;
}
