#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef int ll;
vector<vector<pair<ll,ll> > >v;
ll x,y,ans=1e9,p[200009],k;
bool b[200009];
deque<ll>dq;
map<ll,ll>op,mp;
void dfs(ll d,ll pp)
{
p[d]=1;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
dfs(z.f,d);
p[d]+=p[z.f];
}
}
ll center(ll d,ll pp)
{
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
if(p[z.f]*2>y)
return center(z.f,d);
}
return d;
}
void add(ll d,ll pp,ll sum,ll h)
{
if(sum>k)
return;
if(mp[sum])
mp[sum]=min(mp[sum],h);
else
mp[sum]=h;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
add(z.f,d,sum+z.s,h+1);
}
}
int best_path(ll n, ll K, ll H[][2], ll co[])
{
k=K;
if(k==0)
return 0;
v.resize(n);
for(ll i=0; i<n-1; i++)
{
x=H[i][0], y=H[i][1];
v[x].push_back({y,co[i]});
v[y].push_back({x,co[i]});
}
dq.push_back(0);
while(dq.size())
{
x=dq.front();
dq.pop_front();
dfs(x,-1);
y=p[x];
x=center(x,-1);
op.clear();
b[x]=1;
for(auto z:v[x])
{
if(b[z.f])
continue;
mp.clear();
add(z.f,x,z.s,1);
for(auto u:mp)
{
if(u.s==0)
continue;
if(u.f==k)
ans = min(ans, u.s);
if(op[k-u.f])
ans = min(ans, u.s+op[k-u.f]);
if(op[u.f])
op[u.f] = min(op[u.f],u.s);
else
op[u.f] = u.s;
}
dq.push_back(z.f);
}
}
if(ans==1e9)
ans=-1;
//cout<<ans<<endl;
return ans;
}
