#include <bits/stdc++.h>
using namespace std;
//#include "race.h"
#define int long long
int n,k;
#define MAXN 200007
unordered_map<int, int> al[MAXN];
int ans = 2*MAXN;
unordered_map<int, int> merger[MAXN];
int offset[MAXN] = {0};
int valoffset[MAXN] = {0};
int dfs(int node, int p){
int largest = -1, largestVal = -1;
int totalSize = 1;
for (auto x : al[node]){
if (x.first == p) continue;
int ss = dfs(x.first, node);
totalSize += ss;
if (ss > largestVal){
largestVal = ss; largest = x.first;
}
}
//we need to merge while checking :D
if (largest != -1){
swap(merger[node], merger[largest]);
offset[node] = offset[largest] + al[node][largest];
valoffset[node] = valoffset[largest] + 1;
merger[node][-offset[node]] = -valoffset[node];
if (merger[node].count(k - offset[node]) != 0){
int torture = merger[node][k - offset[node]];
ans = min(ans, torture + valoffset[node]);
}
for (auto x : al[node]){
if (x.first == p || x.first == largest) continue;
for (auto y : merger[x.first]){
//check if x.second + y.first - offset[x.first] can form k with a value from (merger[node]) but offset by offset[node]
//check if k - (x.second + y.first - offset[x.first] - offset[node]) can be found
int trueValSec = y.first + offset[x.first] + al[node][x.first];
//cerr << node << ' ' << x.first << ' ' << trueValSec << ' ' << k - trueValSec + offset[node] << '\n';
/*
cout << "For node " << node << '\n';
for (auto x : merger[node]){
if (x.first + offset[node] == k){
//ans = min(ans, x.second + valoffset[node]);
}
cout << x.first + offset[node] << ' ' << x.second + valoffset[node] << '\n';
}
* */
//we want k = trueval + trueValSec
//k - truevalSec = trueVal
//k - trueValSec = valFound - offset
//k - trueValSec + offset[node] = valFound
//valFound = trueval + offset[]
//if (node == 0 && x.first == 1) cout << trueValSec << ' ' << k - trueValSec - offset[node] << "\n\n\n";
if (merger[node].count(k - trueValSec - offset[node]) != 0){
int torture = merger[node][k - trueValSec - offset[node]] + valoffset[x.first];
ans = min(ans, torture + y.second + valoffset[node] + 1);
}
}
for (auto y : merger[x.first]){
int intendedAdd = y.first + offset[x.first] - offset[node] + x.second;
if (merger[node].count(intendedAdd) == 0 || merger[node][intendedAdd] > y.second + 1 - valoffset[x.first] - valoffset[node]){
merger[node][intendedAdd] = y.second + 1 + valoffset[x.first] - valoffset[node];
}
}
}
}
merger[node][-offset[node]] = -valoffset[node];
//cout << "For node " << node << '\n';
if (merger[node].count(k - offset[node]) != 0){
ans = min(ans, merger[node][k - offset[node]] + valoffset[node]);
}
/*
for (auto x : merger[node]){
if (x.first + offset[node] == k){
ans = min(ans, x.second + valoffset[node]);
}
//cout << x.first + offset[node] << ' ' << x.second + valoffset[node] << '\n';
}
*/
return totalSize;
}
mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int a, int b) {
return uniform_int_distribution<int>(a, b)(mt_rng);
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
n = N;
k = K;
for (int x = 0; x < n-1; x++){
int a, b; a = H[x][0], b = H[x][1];
al[a][b] = L[x];
al[b][a] = L[x];
}
dfs(randint(0, n-1), -1);
if (ans > MAXN) return -1;
return ans;
}
/*
main(){
int32_t H[][2] = {{0,1},{1,2},{1,3}, {0,4},{4,5},{4,6}};
int32_t L[] = {4,3,2,50,7,9};
cout << best_path(7, 56, H, L);
}
*/
