#include "race.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 2e5 + 5;
constexpr int VALMAX = 1e6 + 5;
constexpr int INF = 1e9;
typedef pair <int, int> PII;
int ans;
vector <PII> G[NMAX];
int Dist;
int Sz[NMAX];
bool sel[NMAX];
int cnt = 0;
PII fr[VALMAX];
void AddToSolution (int Node, int dad, int cost, int Length) {
if (cost > Dist) return;
int remain = Dist - cost;
if (fr[remain].first == cnt)
ans = min(ans, fr[remain].second + Length);
for (auto it : G[Node]) {
int to = it.first;
int c = it.second;
if (to == dad || sel[to]) continue;
AddToSolution(to, Node, cost + c, Length+1);
}
}
void ChangeFR (int Node, int dad, int cost, int Length) {
if (cost > Dist) return;
if (fr[cost].first == cnt)
fr[cost].second = min(fr[cost].second, Length);
else {
fr[cost].first = cnt;
fr[cost].second = Length;
}
for (auto it : G[Node]) {
int to = it.first;
int c = it.second;
if (to == dad || sel[to]) continue;
ChangeFR(to, Node, cost + c, Length+1);
}
}
void Dfs (int Node, int dad = -1) {
Sz[Node] = 1;
for (auto it : G[Node]) {
int to = it.first;
if (to == dad || sel[to]) continue;
Dfs(to, Node);
Sz[Node] += Sz[to];
}
}
int Size;
int centr;
int Centroid (int Node, int dad = -1) {
int Max = Size - Sz[Node];
for (auto it : G[Node]) {
int to = it.first;
if (to == dad || sel[to]) continue;
int x = Centroid(to, Node);
if (x != -1) return x;
Max = max(Max, Sz[to]);
}
if (Max <= (Size + 1) / 2) return Node;
return -1;
}
void Get (int Root) {
Dfs(Root);
Size = Sz[Root];
centr = Centroid(Root);
sel[centr] = 1;
++ cnt;
fr[0].first = cnt;
fr[0].second = 0;
for (auto it : G[centr]) {
int to = it.first;
AddToSolution(to, centr, it.second, 1);
ChangeFR(to, centr, it.second, 1);
}
for (auto it : G[centr]) {
int to = it.first;
if (sel[to]) continue;
Get(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans = INF;
Dist = K;
for (int i = 0; i < N-1; ++ i ) {
G[H[i][0]].push_back({H[i][1], L[i]});
G[H[i][1]].push_back({H[i][0], L[i]});
}
Get(0);
if (ans == INF) return -1;
else return ans;
}
