#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> sz, del;
int ans = INT_MAX;
int dfs_sz(int u, int p)
{
sz[u] = 1;
for (auto [v, w] : adj[u])
{
if (v != p && !del[v])
{
sz[u] += dfs_sz(v, u);
}
}
return sz[u];
}
int centroid(int u, int p, int n)
{
for (auto [v, w] : adj[u])
{
if (v != p && !del[v] && sz[v] > n / 2) return centroid(v, u, n);
}
return u;
}
int t = 1, f;
const int MAXK = 1e6 + 1;
int has[MAXK] = {}, len[MAXK] = {};
void dfs1(int u, int p, int d, int h)
{
if (d > f) return;
if (has[f - d] == t)
{
ans = min(ans, h + len[f - d]);
}
for (auto [v, w] : adj[u])
{
if (v != p && !del[v])
{
dfs1(v, u, d + w, h + 1);
}
}
}
void dfs2(int u, int p, int d, int h)
{
if (d > f) return;
if (has[d] == t)
{
len[d] = min(len[d], h);
}
else
{
has[d] = t;
len[d] = h;
}
for (auto [v, w] : adj[u])
{
if (v != p && !del[v])
{
dfs2(v, u, d + w, h + 1);
}
}
}
void solve(int u)
{
int n = dfs_sz(u, u);
int c = centroid(u, u, n);
del[c] = 1;
t++;
has[0] = t;
len[0] = 0;
for (auto [v, w] : adj[c])
{
if (del[v]) continue;
dfs1(v, v, w, 1);
dfs2(v, v, w, 1);
}
for (auto [v, w] : adj[c]) if (!del[v]) solve(v);
}
int best_path(int N, int K, int H[][2], int L[])
{
f = K;
adj.resize(N);
sz.resize(N);
del.resize(N);
for (int i = 0; i < N - 1; i++)
{
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
solve(0);
return ans == INT_MAX ? -1 : ans;
}
// int main()
// {
// int N = 11;
// int K = 12;
// int H[][2] = {
// {0, 1},
// {0, 2},
// {2, 3},
// {3, 4},
// {4, 5},
// {0, 6},
// {6, 7},
// {6, 8},
// {8, 9},
// {8, 10}
// };
// int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
// cout << best_path(N, K, H, L);
// return 0;
// }
