#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 centroid,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,centroid,dist+cost,edges+1,distances);
}
}
void process(int centroid){
vector<int> dists(K+7); //sum, edges
for (auto [child,cost]:tree[centroid]){
if (removed[child]) continue;
// potrzebuje wszystkie sciezki
vector<pair<int,int>> distances;
getPaths(child,centroid,centroid,cost,1,distances);
for (auto [sum,edges]:distances){
if (dists[K-sum]>0){
ans=min(ans,dists[K-sum]+edges);
}
}
for (auto [sum,edges]:distances){
if (dists[sum]==0) dists[sum]=edges;
else dists[sum]=min(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],vector<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);
}
