#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, long long>> tree[200000];
int k;
set<pair<long long, int>> values[200000];
long long offsets[200000];
int edgeOffsets[200000];
int answer = 1e9;
void dfs(int node, int parent)
{
if (tree[node].size() == 1 && node != 0) return;
int chosen = -1;
int chosenL = -1;
for (auto [child, l] : tree[node])
{
if (child == parent) continue;
dfs(child, node);
if (chosen == -1 || values[child].size() > values[chosen].size())
{
chosen = child;
chosenL = l;
}
}
offsets[node] = offsets[chosen] + chosenL;
edgeOffsets[node] = edgeOffsets[chosen] + 1;
values[node].swap(values[chosen]);
values[node].emplace(-offsets[node] + chosenL, -edgeOffsets[node] + 1);
for (auto [child, l] : tree[node])
{
if (child == parent || child == chosen) continue;
values[child].emplace(offsets[child], -edgeOffsets[child]);
for (auto [s, e] : values[child])
{
int v = k - l - s + offsets[child] - offsets[node];
auto it = values[node].lower_bound(make_pair(v, INT_MIN));
if (it != values[node].end() && it->first == v) answer = min(answer, it->second + e + 1 + edgeOffsets[child] + edgeOffsets[node]);
}
for (auto [s, e] : values[child])
{
int v = l + s + offsets[child] - offsets[node];
values[node].emplace(v, e + edgeOffsets[child] - edgeOffsets[node] + 1);
}
}
auto it = values[node].lower_bound(make_pair(k - offsets[node], INT_MIN));
if (it != values[node].end() && it->first == k - offsets[node]) answer = min(answer, it->second + edgeOffsets[node]);
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; ++i)
{
tree[H[i][0]].emplace_back(H[i][1], L[i]);
tree[H[i][1]].emplace_back(H[i][0], L[i]);
}
if (N == 1) return -1;
dfs(0, -1);
if (answer == 1e9) return -1;
else return answer;
}
