#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include "race.h"
//#include <bits/stdc++.h>
#define in cin
#define out cout
#define mkp make_pair
using namespace std;
int n, k, mini = -1;
vector<int> g[200001], d[200001];
int dim[200001]; // size (local calculat) (you'll see)
int dp[200001]; // dp[i] = dim max a unui subarb daca il elimin pe i (tot local) (you'll also see)
bool acc[200001];
void det_size(int nod, int f){
dim[nod] = 0;
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
det_size(cop, nod);
dim[nod] += dim[cop];
}
dim[nod]++;
}
void det_dp(int nod, int f, int size_subt){
dp[nod] = size_subt - dim[nod];
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
det_dp(cop, nod, size_subt);
dp[nod] = max(dp[nod], dim[cop]);
}
}
int centroidul(int nod, int f, int size_subt){
if(dp[nod] <= size_subt / 2) return nod;
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
int cc = centroidul(cop, nod, size_subt);
if(cc != -1) return cc;
}
return -1;
}
void mergeLeft(map< int, int > & a, map< int, int > b, int add){
for(auto i : b){
auto it = a.find(i.first + add);
if(it == a.end()) a[ i.first + add ] = i.second + 1;
else (*it).second = min((*it).second, i.second + 1);
}
}
map< int, int > drumuri(int nod, int f){
map<int, int> sol;
sol[0] = 0;
int poz = 0;
for(int cop : g[nod]){
if(cop == f || !acc[cop]){ poz++; continue;}
mergeLeft(sol, drumuri(cop, nod), d[nod][poz]);
poz++;
}
return sol;
}
void proc_arb(int nod){
// cout << "Procesam subarborele lui " << nod << '\n';
det_size(nod, -1); det_dp(nod, -1, dim[nod]);
int cen = centroidul(nod, -1, dim[nod]);
// cout << " -- > dp : " << dp[1] << " size = " << dim[1] << '\n';
// cout << " -- > gasim centroidul ca " << cen << '\n';
acc[cen] = 0;
// gasim mapurile
int poz = 0;
map<int, int> general;
for(int cop : g[cen]){
if(!acc[cop]){ poz++; continue;}
// cout << " -- > Facem copilul " << cop << '\n';
map<int, int> mp = drumuri(cop, cen);
// cout << " -- > Are ca drumuri pe : \n";
// for(auto i : mp){
// cout << " -- > " << i.first << " , " << i.second << '\n';
// }
for(auto i : mp){
if(general.find( k - i.first - d[cen][poz] ) == general.end()) continue;
int len = general[k - i.first - d[cen][poz] ] + i.second + 1;
// cout << " -- > Gasesc drum de lungime " << len << '\n';
if(mini == -1 || mini > len) mini = len;
}
mergeLeft(general, mp, d[cen][poz]);
poz++;
}
// cout << "In general : \n";
// for(auto i : general){
// cout << " -- > " << i.first << " , " << i.second << '\n';
// }
for(int cop : g[cen]){
if(!acc[cop]) continue;
proc_arb(cop);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
for(int i = 0; i < n; i++) acc[i] = 1;
for(int i = 0; i < N - 1; i++){
g[ H[i][0] ].push_back( H[i][1] );
g[ H[i][1] ].push_back( H[i][0] );
d[ H[i][0] ].push_back( L[i] );
d[ H[i][1] ].push_back( L[i] );
}
// det_size_si_dp(0, -1);
// cout << "Pentru graful initial, centroidul este : " << centroidul(0, -1) << '\n'; // okke, merge
proc_arb(0);
return mini;
}
// signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int n, k; in >> n >> k;
// int H[n - 1][2], L[n - 1];
// for(int i = 0; i < n - 1; i++) in >> H[i][0] >> H[i][1];
// for(int i = 0; i < n - 1; i++) in >> L[i];
// out << best_path(n, k, H, L) << '\n';
// return 0;
// }
