#include "race.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<unordered_map>
#include<iomanip>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll INF = 1e18;
ll n, k;
vvpll tree;
vll depth, dist;
ll ans = INF;
// Merge a and b into b
void merge(map<ll, ll>&a, map<ll, ll>&b, ll lca) {
ll dist_lca = dist[lca];
ll depth_lca = depth[lca];
if (a.size() > b.size()) swap(a, b);
for (auto& it : a) {
ll du = it.first;
ll minCnt = it.second;
if (b.find((2 * dist_lca + k - du)) == b.end()) {
continue;
}
upmin(ans, minCnt + b[(2 * dist_lca + k - du)] - 2 * depth_lca);
}
//ans += b[k + d_lca];
for (auto& it : a) {
if (b.find(it.first) == b.end()) {
b[it.first] = it.second;
}
else {
b[it.first] = min(b[it.first], it.second);
}
}
}
map<ll, ll> dfs(ll node, ll papa) {
map<ll, ll> cur;
cur[dist[node]] = depth[node];
for (auto& it : tree[node]) {
ll nei = it.first, w = it.second;
if (nei == papa) continue;
dist[nei] = dist[node] + w;
depth[nei] = depth[node] + 1;
map<ll, ll> temp = dfs(nei, node);
merge(temp, cur, node);
}
return cur;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
tree.clear(), tree.resize(n);
depth.clear(), depth.resize(n);
dist.clear(), dist.resize(n); // Distance from root
ans = INF;
rep(i, 0, n - 1) {
tree[H[i][0]].push_back({ H[i][1], L[i] });
tree[H[i][1]].push_back({ H[i][0], L[i] });
}
dfs(0, -1);
if (ans == INF) return -1;
return ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
3 3
0 1 1
1 2 1
-1
*/
