#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<ll, int>>> g;
vector<bool> dead;
vector<int> subtree_size;
int ans = INT_MAX;
void compute_subtree_size(int u, int p)
{
subtree_size[u] = 1;
for (auto[w, v] : g[u])
{
if (v == p || dead[v])
continue;
compute_subtree_size(v, u);
subtree_size[u] += subtree_size[v];
}
}
int find_centroid(int u, int p, int comp)
{
for (auto[w, v] : g[u])
{
if (v == p || dead[v])
continue;
if (subtree_size[v] > comp/2)
return find_centroid(v, u, comp);
}
return u;
}
unordered_map<ll, int> mp;
vector<pair<ll, int>> vals;
void dfs(int u, int p, ll dist, int path)
{
vals.push_back({dist, path});
for (auto[w, v] : g[u])
{
if (v == p || dead[v])
continue;
dfs(v, u, dist+w, path+1);
}
}
void decompose(int u, ll K)
{
compute_subtree_size(u, -1);
int centroid = find_centroid(u, -1, subtree_size[u]);
mp[0] = 0;
for (auto[w, v] : g[centroid])
{
if (dead[v])
continue;
dfs(v, centroid, w, 1);
for (auto vals_i : vals)
if (mp.count(K-vals_i.first))
ans = min(ans, vals_i.second + mp[K-vals_i.first]);
for (auto vals_i : vals)
{
if (!mp.count(vals_i.first))
mp[vals_i.first] = vals_i.second;
else
mp[vals_i.first] = min(mp[vals_i.first], vals_i.second);
}
vals.clear();
}
mp.clear();
dead[centroid] = true;
for (auto[w, v] : g[centroid])
{
if (dead[v])
continue;
decompose(v, K);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
g = vector<vector<pair<ll, int>>>(N);
dead = vector<bool>(N);
subtree_size = vector<int>(N);
for (int i = 0; i < N-1; i++)
{
g[H[i][0]].push_back({L[i], H[i][1]});
g[H[i][1]].push_back({L[i], H[i][0]});
}
decompose(0, K);
int ans1 = ans;
g.clear();
dead.clear();
subtree_size.clear();
ans = INT_MAX;
return ans1;
}
// int main()
// {
// int N = 11;
// int K = 12;
// int H[10][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
// int L[10] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
// cout << best_path(N, K, H, L);
// }
