#include "race.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int maxk = 1e6+10;
const int inf = 0x3f3f3f3f;
int n, k;
vector< pair<int, int> > graph[maxn];
map< llint, llint > s[maxn];
llint sol = inf;
llint ofx[maxn], ofy[maxn];
void solve(int x, int parr) {
//printf("solving: %d %d\n", x, parr);
s[x][0] = 0;
for (auto iter : graph[x]) {
int tren = iter.X;
int cost = iter.Y;
if (tren == parr) continue;
solve(tren, x);
//printf("merging %d %d\n", x, tren);
ofx[tren] += cost;
ofy[tren]++;
if (s[tren].size() > s[x].size()) {
//printf("child is larger\n");
swap(s[tren], s[x]);
swap(ofx[tren], ofx[x]);
swap(ofy[tren], ofy[x]);
}
for (auto iter : s[tren]) {
llint dis = iter.X + ofx[tren];
//printf("trying %lld\n", dis);
if (s[x].count(k - dis - ofx[x]))
sol = min(sol, s[x][k - dis - ofx[x]] + iter.Y + ofy[tren] + ofy[x]);
}
for (auto iter : s[tren]) {
llint dis = iter.X + ofx[tren] - ofx[x];
if (s[x].count(dis)) s[x][dis] = min(s[x][dis], iter.Y + ofy[tren] - ofy[x]);
else s[x][dis] = iter.Y + ofy[tren] - ofy[x];
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < n - 1; i++) {
int a = H[i][0];
int b = H[i][1];
graph[a].push_back({b, L[i]});
graph[b].push_back({a, L[i]});
}
solve(0, -1);
if (sol == inf) return -1;
return sol;
}
