#include "race.h"
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
const int maxn=2e5+10;
vector<pair<int,int> > g[maxn];
pair<pair<int,int> ,map<int,int> > s[maxn];
int merges(pair<pair<int,int> ,map<int,int> > &a,pair<pair<int,int> ,map<int,int> > &b,int c,int k){
b.xx.xx+=c;
b.xx.yy+=1;
if(a.yy.size()<b.yy.size()) swap(a,b);
int ret=INT_MAX;
for(auto &i:b.yy){
if(a.yy.find(k-i.xx-b.xx.xx-a.xx.xx)!=a.yy.end())
ret=min(ret,a.yy[k-i.xx-b.xx.xx-a.xx.xx]+a.xx.yy+i.yy+b.xx.yy);
}
for(auto &i:b.yy){
if(a.yy.find(i.xx+b.xx.xx-a.xx.xx)!=a.yy.end())
a.yy[i.xx+b.xx.xx-a.xx.xx]=min(a.yy[i.xx+b.xx.xx-a.xx.xx],i.yy+b.xx.yy-a.xx.yy);
else
a.yy[i.xx+b.xx.xx-a.xx.xx]=i.yy+b.xx.yy-a.xx.yy;
}
return ret;
}
int dfs(int cvor,int k,int p=-1){
int ret=INT_MAX;
for(pair<int,int> i:g[cvor]){
if(i.xx==p) continue;
ret=min(ret,dfs(i.xx,k,cvor));
ret=min(ret,merges(s[cvor],s[i.xx],i.yy,k));
}
s[cvor].yy[-s[cvor].xx.xx]=-s[cvor].xx.yy;
if(s[cvor].yy.find(k-s[cvor].xx.xx)!=s[cvor].yy.end())
ret=min(ret,s[cvor].yy[k-s[cvor].xx.xx]+s[cvor].xx.yy);
return ret;
}
int best_path(int n, int k, int h[][2], int l[]){
for(int i=0;i<n-1;i++){
g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
}
int ret=dfs(0,k);
return ret==INT_MAX ? -1:ret;
}
