#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;
void dfs(vector<vll> &path, vll &del, vll &dp, ll x, ll prev){
dp[x] = 1;
for(ll i : path[x]){
if(i == prev || del[i])continue;
dfs(path, del, dp, i, x);
dp[x] += dp[i];
}
}
ll cent(vector<vll> &path, vll &del, vll &dp, ll n, ll x, ll prev){
for(ll i : path[x]){
if(i == prev || del[i])continue;
if(dp[i] > n/2) return cent(path, del, dp, n, i, x);
}return x;
}
ll res = 1e9, k;
void dfs1(vector<vll> &path, vector<vll> &wei, vll &del, vector<pairll> &pf, ll x, ll prev, ll tot, ll dep, ll lay){
if(tot > k)return;
if(pf[k-tot].sc == lay){
res = min(res, dep + pf[k-tot].fi);
}
for(ll i = 0; i < path[x].size(); i++){
if(path[x][i] == prev || del[path[x][i]])continue;
dfs1(path, wei, del, pf, path[x][i], x, tot + wei[x][i], dep+1, lay);
}
}
void dfs2(vector<vll> &path, vector<vll> &wei, vll &del, vector<pairll> &pf, ll x, ll prev, ll tot, ll dep, ll lay){
if(tot > k)return;
if(pf[tot].sc == lay){
pf[tot].fi = min(pf[tot].fi, dep);
}else{
pf[tot] = {dep, lay};
}
for(ll i = 0; i < path[x].size(); i++){
if(path[x][i] == prev || del[path[x][i]])continue;
dfs2(path, wei, del, pf, path[x][i], x, tot + wei[x][i], dep+1, lay);
}
}
void c(vector<vll> &path, vector<vll> &wei, vll &del, vector<pairll> &pf, ll x, ll lay){
for(ll i = 0; i < path[x].size(); i++){
if(del[path[x][i]])continue;
dfs1(path, wei, del, pf, path[x][i], x, wei[x][i], 1, lay);
dfs2(path, wei, del, pf, path[x][i], x, wei[x][i], 1, lay);
}
}
void decomp(vector<vll> &path, vector<vll> &wei, vll &del, vll &dp, vector<pairll> &pf, ll x, ll lay){
dfs(path, del, dp, x, -1);
ll cen = cent(path, del, dp, dp[x], x, -1);
// cout << cen << ' ' << lay << endl;
pf[0] = {0, lay};
c(path, wei, del, pf, cen, lay);
del[cen] = 1;
// cout << cen << ' ' << lay << endl;
// cout << res << endl;
for(ll i : path[cen]){
if(del[i])continue;
decomp(path, wei, del, dp, pf, i, lay+1);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ll n = N; k = K;
if(!k)return 0;
vector<vll> path(n);
vector<vll> wei(n);
for(ll i = 0; i < n-1; i++){
path[H[i][0]].pb(H[i][1]); path[H[i][1]].pb(H[i][0]);
wei[H[i][0]].pb(L[i]); wei[H[i][1]].pb(L[i]);
}
vector<pairll> pf(k+1);
vll del(n), dp(n);
decomp(path, wei, del, dp, pf, 1, 1);
if(res == 1e9)return -1;
int ans = res;
return ans;
}
