#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,p[200009],k,ans=1e7;
bool b[200009];
deque<ll>dq;
map<ll,ll>op;
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(op[k-sum]||sum==k)
ans=min(ans,op[k-sum]+h);
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
add(z.f,d,sum+z.s,h+1);
}
}
void ok(ll d,ll pp,ll sum,ll h)
{
if(op[sum])
op[sum]=min(op[sum],h);
else
op[sum]=h;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
ok(z.f,d,sum+z.s,h+1);
}
}
ll 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;
add(z.f,x,z.s,1);
ok(z.f,x,z.s,1);
dq.push_back(z.f);
}
}
if(ans>=n)
ans=-1;
return ans;
}
