#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200001;
vector<pair<int,int>> adj[maxn]; // {vtx, cost}
map<int, int> maps[maxn];
int dep[maxn], dis[maxn], ans;
int k;
void check (int v, int dis_a, int dep_a) {
int dis_b = k + 2 * dis[v] - dis_a;
if (maps[v].count(dis_b)) {
int dep_b = maps[v][dis_b];
ans = min(ans, dep_a + dep_b - 2 * dep[v]);
}
}
void add (int v, int dis_a, int dep_a) {
if (maps[v].count(dis_a)) {
maps[v][dis_a] = min(maps[v][dis_a], dep_a);
} else {
maps[v][dis_a] = dep_a;
}
}
void dfs (int i, int p) {
dep[i] = dep[p] + 1;
int m = -1;
for (auto [j, w] : adj[i]) {
if (j != p) {
dis[j] = dis[i] + w;
dfs(j, i);
if (m == -1 || maps[m].size() < maps[j].size()) m = j;
}
}
if (m != -1) swap(maps[m], maps[i]);
check(i, dis[i], dep[i]);
add(i, dis[i], dep[i]);
for (auto [j, w] : adj[i]) {
if (j != p || j != m) {
for (auto [dis_a, dep_a] : maps[j]) {
check(i, dis_a, dep_a);
}
for (auto [dis_a, dep_a] : maps[j]) {
add(i, dis_a, dep_a);
}
}
}
}
/*
N, K
H[i] -> H[i][0], H[i][1]
L[i] -> weight of H[i]
*/
int best_path(int n, int K, int h[][2], int l[]) {
k = K;
ans = n;
for (int i = 0 ; i < n - 1 ; i++) {
int u = h[i][0], v = h[i][1];
adj[u].push_back({v, l[i]});
adj[v].push_back({u, l[i]});
}
dfs(0, n);
return ans;
}
