#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;
constexpr ll maxn=200005;
ll ans=LONG_LONG_MAX;
ll stSize[maxn];
ll findSTsize(ll u,ll p,vector<vector<pll>> &adj,vll &removed)
{
ll ans=1;
for(auto &[v,w]:adj[u])
{
if(v==p || removed[v])
continue;
ans+=findSTsize(v,u,adj,removed);
}
return stSize[u]=ans;
}
ll findCentroid(ll u,ll p,ll treesize,vector<vector<pll>> &adj,vll &removed)
{
for(auto &[v,w]:adj[u])
{
if(v==p || removed[v])
continue;
if(stSize[v]*2>treesize)
return findCentroid(v,u,treesize,adj,removed);
}
return u;
}
void DFS(ll u,ll p,ll totalweight,ll edgecnt,vector<vector<pll>> &adj,vll &removed,map<ll,ll> &currDistMinEdge)
{
if(currDistMinEdge.find(totalweight)==currDistMinEdge.end())
{
currDistMinEdge[totalweight]=edgecnt;
}
else
{
currDistMinEdge[totalweight]=min(edgecnt,currDistMinEdge[totalweight]);
}
for(auto &[v,w]:adj[u])
{
if(v==p || removed[v])
continue;
DFS(v,u,totalweight+w,edgecnt+1,adj,removed,currDistMinEdge);
}
}
void decompose(ll owo,ll k,vector<vector<pll>> &adj,vll &removed)
{
ll treesize=findSTsize(owo,owo,adj,removed);
ll u=findCentroid(owo,owo,treesize,adj,removed);
removed[u]=1;
map<ll,ll> allDistMinEdge;
allDistMinEdge[0]=0;
for(auto &[v,w]:adj[u])
{
if(removed[v])
continue;
map<ll,ll> currDistMinEdge;
DFS(v,u,w,1,adj,removed,currDistMinEdge);
for(auto &[w,edgecnt]:currDistMinEdge)
{
if(w>k)
continue;
if(allDistMinEdge.find(k-w)==allDistMinEdge.end())
continue;
ans=min(ans,edgecnt+allDistMinEdge[k-w]);
}
for(auto &[w,edgecnt]:currDistMinEdge)
if(allDistMinEdge.find(w)==allDistMinEdge.end())
allDistMinEdge[w]=edgecnt;
else
allDistMinEdge[w]=min(allDistMinEdge[w],edgecnt);
}
for(auto &[v,w]:adj[u])
{
if(removed[v])
continue;
decompose(v,k,adj,removed);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pll>> adj(N,vector<pll>());
for(int i=0;i<N;i++)
{
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
vll removed(N,0);
decompose(0,K,adj,removed);
return (ans == LONG_LONG_MAX ? -1 : ans);
}
