#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int n, k, ans, minSz, curCn, minDistance[10*maxn];
bool isC[maxn];
vector<vector<pair<int, int> > > gr;
vector<int> subSz;
int findCentroid(int x, int p, int dist, int price, int n){
subSz[x] = 1;
int tmpM = 0;
for(auto pr : gr[x]){
int i = pr.first,c = pr.second;
if(isC[i] or i == p){
continue;
}
subSz[x] += findCentroid(i, x, dist+1, price+c, n);
tmpM = max(subSz[i], tmpM);
}
tmpM = max(tmpM, n-subSz[x]);
if(minSz > tmpM){
minSz = tmpM;
curCn = x;
}
return subSz[x];
}
vector<int> chPrices;
void dfs(int x, int p, int dist, int price, bool isAdding){
if(price>=maxn*10){
return;
}
if(isAdding and price < maxn*10){
minDistance[price] = min(minDistance[price],dist);
chPrices.push_back(price);
} else {
if(k - price >= 0){
ans = min(ans, dist + minDistance[k-price]);
}
}
for(auto tmp:gr[x]){
int i = tmp.first, j = tmp.second;
if(isC[i] or i ==p){
continue;
}
dfs(i, x, dist+1, price + j, isAdding);
}
}
void findR(int x, int n){
minSz = 1e9;
curCn = x;
findCentroid(x, -1, 0, 0, n);
isC[curCn] = 1;
for(auto tmp:gr[curCn]){
int i = tmp.first, j = tmp.second;
if(!isC[i]){
dfs(i, curCn, 1, j, 0);
dfs(i, curCn, 1, j, 1);
}
}
unique(chPrices.begin(), chPrices.end());
for(auto x : chPrices){
minDistance[x] = 1e9;
}
minDistance[0] = 0;
chPrices.clear();
for(auto tmp:gr[curCn]){
int i = tmp.first, j = tmp.second;
if(!isC[i]){
findR(i, subSz[i]);
}
}
}
int best_path(int n, int k1, int h[][2], int l[]){
k = k1;
gr.resize(n, vector<pair<int, int> >());
for(int i = 0; i < n-1; ++i){
int x, y, w;
x = h[i][0];
y = h[i][1];
w = l[i];
gr[x].push_back({y, w});
gr[y].push_back({x, w});
}
subSz.resize(n, 0);
for(int i = 1; i < maxn*10; ++i){
minDistance[i] = 1e9;
}
ans = 1e9;
findR(0, n);
if(ans != 1e9){
return ans;
} else {
return -1;
}
}
