#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 200005
#define INF (int)1e9
int ans;
ll k;
map<ll,int> existing,to_add;//(length, min number of edges)
vector<pair<int,ll>> adj[MAXN];//(to,weight)
bool rem[MAXN];//removed during centroid decomposition
int size[MAXN];
int dfs_sz(int curr,int par=-1){//compute sizes
size[curr]=1;
for(auto p:adj[curr]){
int to=p.first;
if(to==par||rem[to]) continue;
size[curr]+=dfs_sz(to,curr);
}
return size[curr];
}
int centroid(int curr,int par,int n){
for(auto p:adj[curr]){
int to=p.first;
if(to==par||rem[to]) continue;
if(size[to]>n/2) return centroid(to,curr,n);
}
return curr;
}
void dfs2(int curr,int par,int num,int len){//paths starting from curr
if(to_add.count(len)) to_add[len]=min(to_add[len],num);
else to_add[len]=num;
//update ans
if(existing.count(k-len)){
ans=min(ans,existing[k-len]+to_add[len]);
}
for(auto p:adj[curr]){
int to=p.first;
ll w=p.second;
if(to==par||rem[to]) continue;
dfs2(to,curr,num+1,len+w);
}
}
void build(int curr){
int n=dfs_sz(curr);
int c=centroid(curr,-1,n);
//find paths from c
existing.clear();
to_add.clear();
existing[0]=0;
for(auto p:adj[c]){
int to=p.first;
ll w=p.second;
if(rem[to]) continue;
dfs2(to,c,1,w);
//merge+clear to_add
for(auto p_:to_add){
ll len=p_.first;
int num=p_.second;
if(existing.count(len)) existing[len]=min(existing[len],num);
else existing[len]=num;
}
to_add.clear();
}
//decompose
rem[c]=true;
for(auto p:adj[c]){
int to=p.first;
if(!rem[to]) build(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans=INF;
k=K;
for(int i=0;i<N;i++){
adj[i].clear();
}
for(int i=0;i<N-1;i++){
int a=H[i][0];
int b=H[i][1];
ll w=L[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
memset(rem,false,sizeof(rem));
//centroid decomposition
build(0);
return ans==INF?-1:ans;
}
