#include <bits/stdc++.h>
using namespace std;
int const INF=1e9;
int const MAX=2e5+5;
int const MAXK=1e6+5;
int subsize[MAX];
int min_len[MAXK];
int get_subsize(int nod,int tata,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
subsize[nod]=1;
for(auto [u,w] : tree[nod])
if(u!=tata && !dead[u])
subsize[nod]+=get_subsize(u,nod,tree,dead);
return subsize[nod];
}
int find_centroid(int nod,int tata,int total_size,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
for(auto [u,w] : tree[nod])
if(u!=tata && !dead[u] && subsize[u]>total_size/2)
return find_centroid(u,nod,total_size,tree,dead);
return nod;
}
void minself(int& x,int val){
if(x>val)
x=val;
}
void insert_values(int nod,int tata,int dist,int len,int K,bool type,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
if(type)
minself(min_len[dist],len);
else
min_len[dist]=INF;
for(auto [u,w] : tree[nod])
if(u!=tata && !dead[u] && dist+w<=K)
insert_values(u,nod,dist+w,len+1,K,type,tree,dead);
}
void query_values(int nod,int tata,int dist,int len,int K,int& ans,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
minself(ans,len+min_len[K-dist]);
for(auto [u,w] : tree[nod])
if(u!=tata && !dead[u] && dist+w<=K)
query_values(u,nod,dist+w,len+1,K,ans,tree,dead);
}
void decompose(int nod,int K,int& ans,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
get_subsize(nod,-1,tree,dead);
int centroid=find_centroid(nod,-1,subsize[nod],tree,dead);
for(auto [u,w] : tree[centroid])
if(!dead[u] && w<=K){
query_values(u,centroid,w,1,K,ans,tree,dead);
insert_values(u,centroid,w,1,K,1,tree,dead);
}
for(auto [u,w] : tree[centroid])
if(!dead[u])
insert_values(u,centroid,w,1,K,0,tree,dead);
min_len[0]=0;
dead[centroid]=1;
for(auto [u,w] : tree[centroid])
if(!dead[u])
decompose(u,K,ans,tree,dead);
}
int best_path(int N,int K,int H[][2],int L[]){
vector<vector<pair<int,int>>>tree;
tree.resize(N+5);
int i;
for(i=0;i<N-1;++i){
auto [u,v]=H[i];
auto w=L[i];
tree[u].push_back({v,w});
tree[v].push_back({u,w});
}
min_len[0]=0;
for(i=1;i<K+5;++i)
min_len[i]=INF;
vector<bool>dead(N+5,0);
int ans=INF;
decompose(0,K,ans,tree,dead);
if(ans<INF)
return ans;
return -1;
}
