#include "bits/stdc++.h"
#include "race.h"
using namespace std;
const int maxn = 200001;
vector<pair<int,int>> adj[maxn];
int sub[maxn];
int k;
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
sub[cur] = 1;
if ((adj[cur].empty()) || (adj[cur].size() == 1 and cur != 0)) {
// maps[cur] = new 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));
sub[cur] += sub[i];
if (mx == -1 || sub[i] > sub[mx]) mx = i;
}
}
// maps[cur] = maps[mx];
swap(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;
}
