#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
// C++
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include "race.h"
using namespace std;
vector<vector< pair<long long,long long> > > g;// {node,dist}
vector<long long> off,offset_node;
void dfs(long long node,long long par,vector<map<long long,long long> > &hash,long long k,long long &ans)
{
for(auto child:g[node])
{
if(child.first==par) continue;
dfs(child.first,node,hash,k,ans);
// }
// for(auto child:g[node])
// {
if(child.first == par) continue;
long long off_node = off[node],off_child=off[child.first],edge=child.second,off_used=off_child;
long long offset_node_used = offset_node[child.first],ll=1;
if(hash[node].size()<hash[child.first].size())
{
// cout<<node<<"*\n";
off_used = off[node];
offset_node_used = offset_node[node];
off[node] = off_child+edge;
offset_node[node] = ll+ offset_node[child.first];
edge=0;
ll=0;
swap(hash[node],hash[child.first]);
}
for(auto it=hash[child.first].begin();it!=hash[child.first].end();it++)
{
long long dist = it->first + off_used + edge;
long long mn_nodes = ll+it->second+offset_node_used;
if(hash[node].find(k-dist-off[node])!=hash[node].end())
ans=min(ans,mn_nodes+hash[node][k-dist-off[node]] + offset_node[node]);
}
for(auto it=hash[child.first].begin();it!=hash[child.first].end();it++)
{
long long dist = it->first + off_used + edge;
long long mn_nodes = ll+it->second+offset_node_used;
// if(hash[node].find(k-dist-off[node])!=hash[node].end())
// ans=min(ans,mn_nodes+hash[node][k-dist-off[node]] + offset_node[node]);
// else if(k==dist+off[node]) ans =min(ans,mn_nodes+offset_node[node]);
if(hash[node].find(dist-off[node])!=hash[node].end())
{
long long v1 = hash[node][dist-off[node]]+offset_node[node];
hash[node][dist-off[node]] = min(v1,mn_nodes)-offset_node[node];
}
else hash[node][dist-off[node]] = mn_nodes-offset_node[node];
}
}
}
// void dfs2(int node,int par,vector<map<long long,long long> > &hash){
// for(auto child:g[node]){
// if(child.first==par) continue;
// if(child.second==0) hash[node][0]=1;
// dfs2(child.first,node,hash);
// }
// }
int best_path(int N, int K, int H[][2], int L[])
{
long long n,k,a,b,wt;
long long ans=1e18;
vector<map<long long,long long> > hash;
n=N;
k=K;
g.resize(n+10);
off.assign(n+10,0);
offset_node.assign(n+10,0);
hash.resize(n+10);
for(long long i=0;i<=n;i++) hash[i][0]=0;
for(long long i=0;i<n-1;i++){
a=H[i][0];
b=H[i][1];
wt=L[i];
g[a].push_back(make_pair(b,wt));
g[b].push_back(make_pair(a,wt));
}
// dfs2(0,-1,hash);
dfs(0,-1,hash,k,ans);
if(ans==1e18) ans=-1;
int ans2=ans;
return ans2;
}
