#include <bits/stdc++.h>
using namespace std;
#define inf 1000*1000*1000
#define ll long long
void FindLeafs(int node, int p, vector<vector<int>> &vecin, queue<int> &Q)
{
if (vecin[node].size() == 1)
Q.push(node);
for (int i = 0; i < vecin[node].size(); i++)
{
if (vecin[node][i] == p)
continue;
FindLeafs(vecin[node][i], node, vecin, Q);
}
}
void wormd_dfs(int node, int p, int k, int &best_ans, int path, int C, vector<vector<int>> &vecin, vector<vector<int>> &cost, vector<int> &seen)
{
if (C == k)
{
best_ans = min(best_ans, path);
return;
}
for(int i = 0; i < vecin[node].size(); i++)
{
auto vec = vecin[node][i];
if (vec == p || seen[vec] == 1)
continue;
wormd_dfs(vec, node, k, best_ans, path + 1, C + cost[node][i], vecin, cost, seen);
}
}
int best_path(int n, int k, int H[][2], int L[])
{
int best_ans = inf;
queue<int> Q;
vector<int> seen(n, 0);
vector<vector<int>> vecin(n), cost(n);
for (int i = 0; i < n-1; i++)
{
vecin[H[i][0]].push_back(H[i][1]);
vecin[H[i][1]].push_back(H[i][0]);
cost[H[i][0]].push_back(L[i]);
cost[H[i][1]].push_back(L[i]);
}
FindLeafs(0, -1, vecin, Q);
while (!Q.empty())
{
auto node = Q.front();
Q.pop();
if (seen[node] != 0)
continue;
seen[node] = 1;
wormd_dfs(node, -1, k, best_ans, 0, 0, vecin, cost, seen);
for (int i = 0; i < vecin[node].size(); i++)
{
if (seen[vecin[node][i]] == 0)
Q.push(vecin[node][i]);
}
}
if (best_ans == inf)
return -1;
return best_ans;
}
