#include <bits/stdc++.h>
using namespace std;
void updateWithMin(map<int, int> &a, int k, int v)
{
if (a.find(k) == a.end())
a[k] = v;
else
a[k] = min(a[k], v);
}
void merge(map<int, int> &a, map<int, int> &b, int l, int &minPath, int totalDis)
{
if (a.size() < b.size())
swap(a, b);
for (auto [nk, v] : b)
{
int k = nk - l;
// Find a complementary path
if (a.find(totalDis - k) != a.end())
minPath = min(minPath, a[totalDis - k] + v + 1);
updateWithMin(a, k, v + 1);
if (k == 0)
minPath = min(minPath, v + 1);
}
}
int best_path(int n, int k, int edges[][2], int wt[])
{
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++)
{
int u = edges[i][0], v = edges[i][1], w = wt[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<map<int, int>> paths(n);
for (int i = 0; i < n; i++)
paths[i][k] = 0;
int minPaths = n + 1;
function<void(int, int)> dfs = [&](int u, int p)
{
for (auto [v, w] : g[u])
{
if (v == p)
continue;
dfs(v, u);
merge(paths[u], paths[v], w, minPaths, k);
}
};
dfs(0, -1);
return minPaths == n + 1 ? -1 : minPaths;
}
