#include "bits/stdc++.h"
#include "race.h"
using namespace std;
const int maxn = 200001;
vector<pair<int,int>> adj[maxn];
int k;
unordered_map<long long,int> *maps[maxn];
void Check (int cur, int x, int y, int& ret, int dep2, int dep) {
if (maps[cur] -> count(k + 2 * dep - x)) {
ret = min(ret, y + (*maps[cur])[k + 2 * dep - x] - 2 * dep2);
}
}
void Insert (int cur, int x, int y) {
if (maps[cur] -> count(x)) (*maps[cur])[x] = min((*maps[cur])[x], y);
else (*maps[cur])[x] = y;
}
int dfs (int cur, int par, int dep, int dep2) { // dep = sum of weights // dep2 = number of edges from root
if ((adj[cur].empty()) || (adj[cur].size() == 1 and cur != 0)) {
maps[cur] = new unordered_map<long long, int>();
maps[cur] -> insert({dep, dep2});
return INT_MAX;
}
int mx = -1;
int ret = INT_MAX;
for (auto [i, j] : adj[cur]) {
if (i != par) {
ret = min(ret, dfs(i, cur, dep + j, dep2 + 1));
if (mx == -1 || maps[i] -> size() > maps[mx] -> size()) mx = i;
}
}
maps[cur] = maps[mx];
for (auto [i, j] : adj[cur]) {
if (i != par and i != mx) {
for (auto [x, y] : *maps[i]) {
Check(cur, x, y, ret, dep2, dep);
}
for (auto [x, y] : *maps[i]) {
Insert(cur, x, y);
}
}
}
Check(cur, dep, dep2, ret, dep2, dep);
Insert(cur, dep, dep2);
return ret;
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0 ; i < N - 1 ; i++) {
auto [u, v] = H[i];
int w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
int ans;
return (ans = dfs(0, 0, 0, 0)) == INT_MAX ? -1 : ans;
}
