#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=1e9;
vector<vector<int>>dp;
vector<vector<pair<int,int>>>adj;
int ans=INF;
void dfs(int u=0,int p=-1){
vector<int>&res=dp[u];
int k=res.size()-1;
res[0]=0;
for(auto[v,l]:adj[u]){
if(v==p){
continue;
}
dfs(v,u);
for(int i=0;i<=k&&k-i-l>=0;i++){
ans=min(ans,dp[v][i]+res[k-i-l]+1);
}
for(int i=l;i<=k;i++){
res[i]=min(res[i],dp[v][i-l]+1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
adj.resize(N);
dp=vector<vector<int>>(N,vector<int>(K+1,INF));
for(int i=0;i<N-1;i++){
auto[u,v]=H[i];
int l=L[i];
adj[u].push_back({v,l});
adj[v].push_back({u,l});
}
dfs();
return ans;
}
