#include "race.h"
#include <vector>
#define MAXN 200005
#define MAXK 1000005
#define pii pair < int, int >
#define mp make_pair
using namespace std;
int C, K, tam[MAXN], dead[MAXN], tim[MAXK], arr[MAXK];
vector < pii > Graph[MAXN];
void pre_tam ( int node, int parent )
{
tam[node] = 1;
for ( auto i : Graph[node] )
if ( i.first != parent && !dead[i.first] )
pre_tam ( i.first, node ), tam[node] += tam[i.first];
}
int find_centroid ( int node, int parent, int siz )
{
for ( auto i : Graph[node] )
if ( i.first != parent && 2 * tam[i.first] > siz && !dead[i.first] )
return find_centroid ( i.first, node, siz );
return node;
}
int qry ( int node, int parent, int s, int a )
{
if ( s > K )
return (1 << 30);
int ret = (1<<30);
if ( tim[K - s] == C )
ret = arr[K - s] + a;
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != parent )
ret = min ( qry ( i.first, node, s + i.second, a + 1 ), ret );
return ret;
}
void upd ( int node, int parent, int s, int a )
{
if ( s > K )
return;
if ( tim[s] != C )
{
arr[s] = a;
tim[s] = C;
}
else
arr[s] = min ( arr[s], a );
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != parent )
upd ( i.first, node, s + i.second, a + 1 );
}
int solve ( int node )
{
pre_tam ( node, -1 );
node = find_centroid ( node, -1, tam[node] );
C++;
tim[0] = C;
arr[0] = 0;
int ans = (1<<30);
for ( auto i : Graph[node] )
{
if ( !dead[i.first] )
{
ans = min ( qry ( i.first, node, i.second, 1 ), ans );
upd ( i.first, node, i.second, 1 );
}
}
dead[node] = 1;
for ( auto i : Graph[node] )
if ( !dead[i.first] )
ans = min ( ans, solve ( i.first ) );
return ans;
}
int best_path ( int N, int _k, int H[][2], int L[] )
{
K = _k;
int u, v;
for ( int i = 0; i < N - 1; i++ )
{
u = H[i][0];
v = H[i][1];
Graph[u].push_back ( mp ( v, L[i] ) );
Graph[v].push_back ( mp ( u, L[i] ) );
}
int retval = solve ( 0 );
if ( retval == (1 << 30) )
return -1;
return retval;
}
