#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)
{
int mx_val = 0, mx_node = 0;
for (auto[w, v] : g[u])
{
if (v == p || dead[v])
continue;
if (subtree_size[v] > mx_val)
{
mx_val = subtree_size[v];
mx_node = v;
}
}
if (mx_val <= comp/2)
return u;
else
return find_centroid(mx_node, u, comp);
}
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]);
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();
}
if (mp.count(K))
ans = min(ans, mp[K]);
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;
}
