#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> tree;
vector<int> subSizes;
vector<bool> removed;
int K;
int ans=INT_MAX;
int getSubSize(int node,int parent){
subSizes[node]=1;
for (auto [child,cost]:tree[node]){
if (child==parent || removed[child]) continue;
subSizes[node]+=getSubSize(child,node);
}
return subSizes[node];
}
int getCentroid(int node,int parent,int subSize){
for (auto [child,cost]:tree[node]){
if (child==parent || removed[child]) continue;
if (subSizes[child]*2>subSize) return getCentroid(child,node,subSize);
}
return node;
}
void getPaths(int node,int parent,int dist,int edges,vector<pair<int,int>> &distances){
if (dist>K) return;
distances.emplace_back(dist,edges);
for (auto [child,cost]:tree[node]){
if (child==parent || removed[child]) continue;
getPaths(child,node,dist+cost,edges+1,distances);
}
}
void process(int centroid){
unordered_map<int,int> dists;
dists[0]=0;
for (auto [child,cost]:tree[centroid]){
if (removed[child]) continue;
// potrzebuje wszystkie sciezki
vector<pair<int,int>> distances;
getPaths(child,centroid,cost,1,distances);
for (auto [sum,edges]:distances){
if (dists.count(K-sum)){
ans=min(ans,dists[K-sum]+edges);
}
}
for (auto [sum,edges]:distances){
if (dists.count(sum)) dists[sum]=min(dists[sum],edges);
else dists[sum]=edges;
}
}
}
void decomp(int node){
int centroid=getCentroid(node,-1,getSubSize(node,-1));
process(centroid);
removed[centroid]=true;
for (auto [child,cost]:tree[centroid]){
if (removed[child]) continue;
decomp(child);
}
}
int best_path(int n,int k,int h[][2],int l[]){
ans=INT_MAX;
K=k;
tree.clear();
subSizes.clear();
removed.clear();
tree.resize(n+1);
subSizes.resize(n+1);
removed.resize(n+1);
for (int i=0;i<n-1;i++){
int u=h[i][0];
int v=h[i][1];
int price=l[i];
tree[u].emplace_back(v,price);
tree[v].emplace_back(u,price);
}
decomp(1);
return (ans!=INT_MAX ? ans : -1);
}
