#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int MAXA = 1000010;
const int INF = 1e8;
int n, k;
vector<int> ar[MAXN];
vector<int> wg[MAXN];
int tam;
int sub[MAXN];
int marc[MAXN];
int minProf[MAXA];
int ans;
void centDecomp(int cur);
void preCalc(int cur, int pai);
int getCent(int cur, int pai);
void getAns(int cur, int pai, int prof, int dist);
void addProf(int cur, int pai, int prof, int dist);
void removeProf(int cur, int pai, int dist);
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0; i < n - 1; i++){
ar[H[i][0]].push_back(H[i][1]);
ar[H[i][1]].push_back(H[i][0]);
wg[H[i][0]].push_back(L[i]);
wg[H[i][1]].push_back(L[i]);
}
for(int i = 0; i <= k; i++)
minProf[i] = INF;
ans = INF;
centDecomp(1);
return ans;
}
void centDecomp(int cur){
tam = 0;
preCalc(cur, cur);
int cent = getCent(cur, cur);
marc[cent] = 1;
minProf[0] = 0;
for(int i = 0; i < ar[cent].size(); i++){
int viz = ar[cent][i];
if(marc[viz]) continue;
getAns(viz, cent, 1, wg[cent][i]);
addProf(viz, cent, 1, wg[cent][i]);
}
removeProf(cent, cent, 0);
}
void preCalc(int cur, int pai){
tam++;
sub[cur] = 1;
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(viz == pai || marc[viz]) continue;
preCalc(viz, cur);
sub[cur] += sub[viz];
}
}
int getCent(int cur, int pai){
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(viz == pai || marc[viz] || sub[viz] < tam / 2) continue;
return getCent(viz, cur);
}
return cur;
}
void getAns(int cur, int pai, int prof, int dist){
if(dist <= k) ans = min(ans, minProf[k - dist] + prof);
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(viz == pai || marc[viz]) continue;
getAns(viz, cur, prof + 1, dist + wg[cur][i]);
}
}
void addProf(int cur, int pai, int prof, int dist){
minProf[dist] = min(minProf[dist], prof);
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(viz == pai || marc[viz]) continue;
addProf(viz, cur, prof + 1, dist + wg[cur][i]);
}
}
void removeProf(int cur, int pai, int dist){
minProf[dist] = INF;
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(viz == pai || marc[viz]) continue;
removeProf(viz, cur, dist + wg[cur][i]);
}
}
