#include "race.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
using int2 = pair<int, int>;
using ll = long long;
using ll2 = pair<ll, ll>;
#define f first
#define s second
#define all(x) begin(x), end(x)
struct Paths {
ll2 d = {0, 0};
map<ll, ll> m;
};
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';
Paths dfs(v<v<int2>> &adj, int &ans, int k, int node, int prev) {
Paths cur;
// find all unions of paths
v<Paths> paths;
for (auto next : adj[node]) {
if (next.f != prev) {
paths.push_back(dfs(adj, ans, k, next.f, node));
}
}
Paths halves;
sort(all(paths), [](Paths &a, Paths &b) { return a.m.size() < b.m.size(); });
for (int i = 0; i < paths.size(); i++) {
if (paths[i].m.size() > halves.m.size()) {
swap(paths[i], halves);
}
for (auto x : paths[i].m) {
ll cost = x.f + paths[i].d.f;
if (halves.m.count(k - cost - halves.d.f)) {
ans = min(ans, (int)(x.s + paths[i].d.s +
halves.m[k - cost - halves.d.f] + halves.d.s));
}
}
if (i != paths.size() - 1) {
for (auto x : paths[i].m) {
ll cost = x.f + paths[i].d.f;
ll vx = x.s + paths[i].d.s;
if (cost < k && vx < ans) {
if (halves.m.count(cost - halves.d.f)) {
halves.m[cost - halves.d.f] =
min(halves.m[cost - halves.d.f], vx - halves.d.s);
} else {
halves.m[cost - halves.d.f] = vx - halves.d.s;
}
}
}
}
}
// construct new path set
for (auto next : adj[node]) {
if (next.f != prev) {
Paths p = dfs(adj, ans, k, next.f, node);
if (p.m.size() > cur.m.size()) {
swap(p, cur);
cur.d.f += next.s;
cur.d.s += 1;
} else {
p.d.f += next.s;
p.d.s += 1;
}
for (auto x : p.m) {
ll cost = x.f + p.d.f;
// dbg(cost);
ll vx = x.s + p.d.s;
if (cost < k && vx < ans) {
if (cur.m.count(cost - cur.d.f)) {
cur.m[cost - cur.d.f] = min(cur.m[cost], vx - cur.d.s);
} else {
cur.m[cost - cur.d.f] = vx - cur.d.s;
}
}
}
cur.m[next.s - cur.d.f] = 1 - cur.d.s;
}
}
if (cur.m.count(k - cur.d.f)) {
// dbg(node);
// dbg(cur.m[k - cur.d.f]);
ans = min(ans, (int)(cur.m[k - cur.d.f] + cur.d.s));
}
return cur;
}
int best_path(int N, int K, int H[][2], int L[]) {
int ans = INT_MAX;
v<v<int2>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
Paths p = dfs(adj, ans, K, 0, -1);
if (ans == INT_MAX)
ans = -1;
return ans;
}
