#pragma GCC optimize ("Ofast", "unroll-loops")
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
const int NMAX = 200002;
using ll = long long;
const int INF = 21e8;
struct muchii {
int nod, dist;
};
vector <vector <muchii>> v;
int n, k;
bool f[NMAX]; ///dc deja am procesat ca centroid respectivul sau nu
int parent[NMAX];
int weight[NMAX]; ///ce weight are subarb resp
void dfssize(int start) {
weight[start] = 0;
for(auto x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
parent[x.nod] = start;
dfssize(x.nod);
weight[start] += weight[x.nod];
}
weight[start]++;
}
int centroid = -1;
void dfscentroid(int start, int sizee, int tot) { ///sizeul e de sus
bool ok = 0;
if(sizee > tot / 2)
ok = 1;
for(auto x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
if(weight[x.nod] > tot / 2)
ok = 1;
}
if(!ok) { ///am gasit centroidul
centroid = start;
return;
}
for(auto x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
dfscentroid(x.nod, sizee + weight[start] - weight[x.nod], tot);
}
}
unordered_map <ll, int> umap[NMAX];
int ans = INF; ///dist minima pt suma k
void updateans(int start) {
unordered_map <ll, int> lg;
lg.clear();
if(umap[start].find(k) != umap[start].end()) ///dc deja e lant pana in el
ans = min(ans, umap[start][k]);
for(auto x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
for(auto var : umap[x.nod]) { ///COMPARAM cu ce avem de la vechii fii
if(lg.find(k - var.first - x.dist) != lg.end()) {
ans = min(ans, lg[k - var.first - x.dist] + var.second + 1);
}
}
for(auto var : umap[x.nod]) { ///UPDATAM
if(var.first + x.dist > k || (ans < INF && var.second + 1 > ans))
continue;
if(lg.find(var.first + x.dist) != lg.end())
lg[var.first + x.dist] = min(lg[var.first + x.dist], var.second + 1);
else
lg[var.first + x.dist] = var.second + 1;
}
/*if(centroid == 30 && start == 39) {
cout << "try la nodul " << x.nod << '\n';
}*/
}
/*if(centroid == 39 && start == 39) {
cout << "waait so NODUL 38\n";
for(auto var : umap[38])
cout << var.first << " " << var.second << '\n';
cout << "waait so NODUL 40\n";
for(auto var : umap[40])
cout << var.first << " " << var.second << '\n';
}*/
}
void dfsans(int start) { ///pt fiecare centroid, il conectam cu ce am avut
bool ok = 0;
for(auto x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
dfsans(x.nod);
ok = 1;
for(auto var : umap[x.nod]) { ///updatam distantele din x.nod
if(var.first + x.dist > k || (ans < INF && var.second + 1 > ans))
continue;
///first = distanta, second = cate muchii
if(umap[start].find(var.first + x.dist) != umap[start].end())
umap[start][var.first + x.dist] = min(umap[start][var.first + x.dist], var.second + 1);
else
umap[start][var.first + x.dist] = var.second + 1;
}
//umap[start][x.dist] = 1;
}
umap[start][0] = 0; ///frunza SAU pt mai tarziu
if(start == centroid) ///doar pt CENTROID cautam dc exista drumuri de sum k
updateans(centroid);
for(auto x : v[start]) { ///stergem mapurile din fii ca nu ne mai pasa
if(x.nod == parent[start])
continue;
umap[x.nod].clear();
}
/*if(centroid == 39) {
cout << "NODUL " << start << '\n';
for(auto var : umap[start]) {
cout << var.first << " " << var.second << '\n';
}
}*/
}
void build(int start) { ///de la subarborele lui start INCEPEM
parent[start] = -1;
dfssize(start);
centroid = -1;
dfscentroid(start, 0, weight[start]);
//cout << weight[start] << " ";
parent[centroid] = -1; ///rebuild in subarborele nostru sizeurile de parinti etc
dfssize(centroid); ///reindexam parintii basically
dfsans(centroid); ///bifam pt el
f[centroid] = 1;
umap[centroid].clear();
//cout << start << " " << centroid << " " << ans << '\n';
/*if(centroid == 39) {
cout << "yoo\n";
for(int i = 0; i < n; i++)
cout << i << " " << f[i] << '\n';
cout << '\n';
}*/
for(auto x : v[centroid]) { ///facem si in subarbori
if(!f[x.nod])
build(x.nod);
}
}
int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
n = N, k = K;
v.resize(n + 1);
for(int i = 0; i < n - 1; i++) {
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
/*for(int i = 0; i < n; i++) {
cout << "nodul " << i << '\n';
for(auto x : v[i])
cout << x.nod << " ";
cout << '\n';
}*/
build(0);
if(ans == INF)
ans = -1;
return ans;
}
