#include <bits/stdc++.h>
using namespace std;
int N, K, sol = INT_MAX;
int SIZE[200006], DP[200006], W[200006], D[1000006];
bool V[200006];
vector <pair <int, int>> VG[200006];
inline void SDFS(int node, int parent = -1)
{
SIZE[node] = 1;
for(pair <int, int> p : VG[node])
{
if((p.second == parent) || V[p.second]) continue;
SDFS(p.second, node);
SIZE[node] += SIZE[p.second];
}
return;
}
inline int CDFS(int node, int n, int parent = -1)
{
for(pair <int, int> p : VG[node])
{
if((p.second == parent) || V[p.second]) continue;
if(SIZE[p.second] > n) return CDFS(p.second, n, node);
}
return node;
}
inline void DFS1(int node, int parent = -1)
{
if(W[node] > K) return;
if(D[K - W[node]] != INT_MAX) sol = min(DP[node] + D[K - W[node]], sol);
for(pair <int, int> p : VG[node])
{
if((p.second == parent) || V[p.second]) continue;
DP[p.second] = DP[node] + 1;
W[p.second] = W[node] + p.first;
DFS1(p.second, node);
}
return;
}
inline void DFS2(int node, int parent = -1)
{
if(W[node] > K) return;
D[W[node]] = min(DP[node], D[W[node]]);
for(pair <int, int> p : VG[node])
{
if((p.second == parent) || V[p.second]) continue;
DFS2(p.second, node);
}
return;
}
inline void CLEARDFS(int node, int parent = -1)
{
if(W[node] > K) return;
D[W[node]] = INT_MAX;
for(pair <int, int> p : VG[node])
{
if((p.second == parent) || V[p.second]) continue;
CLEARDFS(p.second, node);
}
return;
}
inline void CD(int root)
{
SDFS(root);
int centroid = CDFS(root, SIZE[root] >> 1);
V[centroid] = true;
D[0] = 0;
for(pair <int, int> p : VG[centroid])
{
if(V[p.second]) continue;
DP[p.second] = 1;
W[p.second] = p.first;
DFS1(p.second, centroid);
DFS2(p.second, centroid);
}
W[centroid] = 0;
CLEARDFS(centroid);
for(pair <int, int> p : VG[centroid]) if(!V[p.second]) CD(p.second);
}
int best_path(int n, int k, int (*H)[2], int* L)
{
N = n;
K = k;
for(int i = 0; i < N - 1; i++)
{
VG[H[i][0] + 1].push_back({L[i], H[i][1] + 1});
VG[H[i][1] + 1].push_back({L[i], H[i][0] + 1});
}
for(int i = 0; i <= K; i++) D[i] = INT_MAX;
CD(1);
if(sol == INT_MAX) return -1;
return sol;
}
