#include "race.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5+5;
const int INF = 1e9;
vector<pii> adj[N];
int K, answer;
int dp[N][105];
void dfs(int nd, int pr){
dp[nd][0] = 0;
for (int i = 1; i <= K; i++)
dp[nd][i] = INF;
for (auto [c, e]: adj[nd]){
if (c == pr)
continue;
dfs(c, nd);
//update answer
for (int w1 = 0; w1 + e <= K; w1++){
int w2 = K - e - w1;
answer = min(answer, dp[nd][w1] + dp[c][w2]+1);
}
//update dp
for (int p = 0; p+e <= K; p++)
dp[nd][p+e] = min(dp[nd][p+e],dp[c][p]+1);
}
}
void dfs1(int nd, int pr, int lvl, ll weight){
if (weight == K)
answer = min(answer, lvl);
if (weight >= K)
return;
for (auto [c, e]: adj[nd]){
if (c == pr)
continue;
dfs1(c, nd, lvl+1, weight+e);
}
}
map<ll, int> m[N];
void dfs2(int nd, int pr, ll W, int L){
m[nd].clear();
m[nd][W] = L;
for (auto [c, e]: adj[nd]){
if (c == pr)
continue;
dfs2(c, nd, W+e, L+1);
if (m[nd].size() < m[c].size())
swap(m[nd], m[c]);
//update answer
for (auto [w1, l1]: m[c]){
int w2 = K - w1 + 2*W;
if (m[nd].find(w2) != m[nd].end()){
int l2 = m[nd][w2];
answer = min(answer, l1 + l2 - 2*L);
}
}
//update map
for (auto [w1, l1]: m[c]){
if (m[nd].find(w1) == m[nd].end())
m[nd][w1] = l1;
else
m[nd][w1] = min(m[nd][w1], l1);
}
m[c].clear();
}
}
int best_path(int n, int k, int H[][2], int L[]){
K = k;
answer = INF;
for (int i = 0; i < n - 1; i++){
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
if (k <= 100) //subtask 1 and 3
dfs(1, -1);
else if(n <= 1000){ //subtask 2
for (int i = 0; i < n; i++)
dfs1(i, -1, 0, 0);
}
else{
dfs2(1, -1, 0, 0);
}
if (answer == INF)
answer = -1;
return answer;
}
