#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
int n, k;
const int INF = 1e9;
const int MAXN = 2e5 + 7;
vector<pair<int, int>> graf[MAXN];
int ile_pod[MAXN];
bool czy_centroid[MAXN];
const int MAXK = 1e6 + 2;
int ans = INF;
int jaka[MAXK];
int depth[MAXN];
queue<pair<int, int>> jakie;
queue<int> cofnij;
void dfs(int v, int last, int dl) {
// cout << "v = " << v << " dl = " << dl << '\n';
depth[v] = depth[last] + 1;
ile_pod[v] = 0;
dl = min(dl, k + 1);
if (dl <= k) {
// cout << "XX" << '\n';
ans = min(ans, jaka[k - dl] + depth[v] - 1);
jakie.push({dl, depth[v] - 1});
cofnij.push(dl);
}
for (auto syn: graf[v]) {
if (syn.first == last || czy_centroid[syn.first]) {
continue;
}
dfs(syn.first, v, dl + syn.second);
ile_pod[v] += (ile_pod[syn.first] + 1);
if (depth[v] == 1) {
// cout << "POC" << '\n';
while (!jakie.empty()) {
int a = jakie.front().first;
int b = jakie.front().second;
jaka[a] = min(jaka[a], b);
// cout << "v = " << v << " a = " << a << " b = " << b << '\n';
jakie.pop();
}
// cout << "KON" << '\n';
}
}
}
int find_centroid(int v, int last, int sz) {
int w = v;
for (auto syn: graf[v]) {
if (syn.first == last || czy_centroid[syn.first]) {
continue;
}
// cout << "syn = " << syn.first << " ilepod = " << ile_pod[syn.first] << " size = " << sz << '\n';
if (ile_pod[syn.first] + 1 >= (sz/2)) {
w = find_centroid(syn.first, v, sz);
}
}
return w;
}
void centroid_decomposition(int v, int sz) {
int centre = find_centroid(v, v, sz);
depth[centre] = 0;
// cout << "centre = " << centre << '\n';
czy_centroid[centre] = true;
jaka[0] = 0;
dfs(centre, centre, 0);
while (!cofnij.empty()) {
// cout << "x = " << cofnij.front() << '\n';
jaka[cofnij.front()] = INF;
cofnij.pop();
}
for (auto syn: graf[centre]) {
if (czy_centroid[syn.first]) {
continue;
}
centroid_decomposition(syn.first, ile_pod[syn.first] + 1);
}
}
int best_path(int pom1, int pom2, int H[][2], int L[])
{
n = pom1;
k = pom2;
rep(i, k + 1) {
jaka[i] = INF;
}
rep(i, n - 1) {
int a = H[i][0];
int b = H[i][1];
int waga = L[i];
graf[a].push_back({b, waga});
graf[b].push_back({a, waga});
}
dfs(0, 0, 0);
while (!cofnij.empty()) {
jaka[cofnij.front()] = INF;
cofnij.pop();
}
centroid_decomposition(0, n);
if (ans >= INF) {
return -1;
}
return ans;
}
