#include<bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define N 200005
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int n_ini;
int k;
int fin_ans;
map<int, int>edge[N];
vector<int>gr[N];
int sz[N];
int dp[1000005];
int par[N];
bool vis[N];
void init_all(int n)
{
for (int i = 0; i <= n; i++)
gr[i].clear(), par[i] = 0, vis[i] = 0, sz[i] = 0, dp[i] = inf;
for (int i = 0; i <= 1000000; i++)
dp[i] = inf;
}
int init_size(int node, int p)
{
if (vis[node] == 1)
return 0;
int ans = 0;
for (auto child : gr[node])
{
if (child != p)
{
ans += init_size(child, node);
}
}
return sz[node] = ans + 1;
}
int get_centroid(int node, int p, int n)
{
for (auto child : gr[node])
{
if (!vis[child] && child != p)
{
if (sz[child] > n / 2)
return get_centroid(child, node, n);
}
}
return node;
}
void make_inf(int node, int par, int val)
{
if (val > k)
return;
dp[val] = inf;
for (auto child : gr[node])
{
if ((vis[child] == 0) && child != par)
{
make_inf(child, node, val + edge[node][child]);
}
}
}
void dfs(int node, int par, int d, int num_node)
{
int need = k - d;
// cout << node << " " << need << " " << num_node << " " << dp[need] << " " << fin_ans << endl;
if (need >= 0)
fin_ans = min(fin_ans, num_node + dp[need]);
else
return;
for (auto child : gr[node])
{
if ((vis[child] == 0) && par != child)
{
dfs(child, node, d + edge[node][child], num_node + 1);
}
}
}
void dfs2(int node, int par, int d, int num_node)
{
dp[d] = min(dp[d], num_node);
if (d > k)
return;
for (auto child : gr[node])
{
if ((vis[child] == 0) & child != par)
dfs2(child, node, d + edge[node][child], d + 1);
}
}
void init_centroid(int node, int p)
{
init_size(node, 0);
int c = get_centroid(node, 0, sz[node]);
vis[c] = 1;
par[c] = p;
dp[0] = 0;
//cout << c << " ->" << fin_ans << " fin_ans" << endl;
for (auto child : gr[c])
{
//cout << child << " " << vis[child] << endl;
if (vis[child] == 0)
{
dfs(child, c, edge[c][child], 1);
dfs2(child, c, edge[c][child], 1);
}
}
make_inf(c, 0, 0);
for (auto child : gr[c])
{
if (!vis[child])
{
// cout << "comr\n";
init_centroid(child, c);
}
}
}
int32_t best_path(int32_t n, int32_t b, int32_t H[][2], int32_t L[])
{
k = (int)b;
n_ini = (int)n;
fin_ans = inf;
init_all(n_ini);
for (int i = 0; i < n - 1; i++)
{
int a, b, c;
a = (int)H[i][0]; b = (int)H[i][1]; c =(int)L[i];
a++; b++;
gr[a].pb(b);
gr[b].pb(a);
edge[a][b] = c;
edge[b][a] = c;
}
init_centroid(1, 0);
if (fin_ans >= inf)
return -1;
else
return (int32_t)fin_ans;
}
