#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const int MAXK=1e6+6;
const int lg=21;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int n,k;
vector<int>dfs_order;
ll depth[MAXN],depth1[MAXN];
int wherel[MAXN],wherer[MAXN];
pair<int,int> dp[3*MAXN][lg];
int pw[3*MAXN];
bool f[MAXN];
int st[MAXN],root;
ll minh[MAXK],ans=MAXN+2;
int rankc[MAXN];
vector<int>updated;
void dfs(int u,int p)
{
dfs_order.push_back(u);
for(auto v:g[u])
{
if(v.first==p)continue;
depth[v.first]=depth[u]+1;
depth1[v.first]=depth1[u]+v.second;
dfs(v.first,u);
dfs_order.push_back(u);
}
}
void precompute()
{
int t=1,cnt=0;
for(int i=1;i<3*MAXN;i++)
{
if(t*2<=i)
{
t*=2;cnt++;
}
pw[i]=cnt;
}
for(int i=0;i<dfs_order.size();i++)
{
wherer[dfs_order[i]]=i;
}
for(int i=dfs_order.size()-1;i>=0;i--)
{
wherel[dfs_order[i]]=i;
}
for(int i=0;i<dfs_order.size();i++)
{
dp[i][0]={depth[dfs_order[i]],dfs_order[i]};
}
for(int step=1;step<lg;step++)
{
for(int i=0;i<dfs_order.size();i++)
{
dp[i][step]=dp[i][step-1];
if(i+(1<<(step-1))<dfs_order.size())
{
dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]);
}
}
}
}
int lca(int x,int y)
{
if(wherel[x]>wherel[y])swap(x,y);
pair<int,int>ret;
int i1=wherel[x],i2=wherer[y];
int d=i2-i1+1;
int l=pw[d];
ret=dp[i1][l];
ret=min(ret,dp[i2-(1<<l)+1][l]);
return ret.second;
}
void dfs1(int u,int p)
{
st[u]=1;
for(auto v:g[u])
{
if(v.first==p)continue;
if(f[v.first])continue;
dfs1(v.first,u);
st[u]+=st[v.first];
}
}
int find(int u,int p,int t)
{
for(auto v:g[u])
{
if(v.first==p)continue;
if(f[v.first])continue;
if(st[v.first]>t/2)
{
return find(v.first,u,t);
}
}
return u;
}
void decompose(int u,int p)
{
dfs1(u,-1);
int c=find(u,-1,st[u]);
if(p!=-1)
{
rankc[c]=rankc[p]+1;
g1[p].push_back(c);
}
else
{
root=c;
rankc[c]=1;
}
f[c]=1;
for(auto v:g[c])
{
if(f[v.first])continue;
decompose(v.first,c);
}
}
void dfs2(int u,int p,int maxrank,int d,int d1)
{
minh[d1]=min(minh[d1],(ll)d);
for(auto v:g[u])
{
if(v.first==p)continue;
if(rankc[v.first]>=maxrank)continue;
if(v.second+d1>k)continue;
dfs2(v.first,u,maxrank,d+1,d1+v.second);
}
}
void dfs3(int u,int p,int maxrank,int d,int d1)
{
ans=min(ans,minh[k-d1]+d);
for(auto v:g[u])
{
if(v.first==p)continue;
if(rankc[v.first]>=maxrank)continue;
if(v.second+d1>k)continue;
dfs3(v.first,u,maxrank,d+1,d1+v.second);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;k=K;
for(int i=0;i<N-1;i++)
{
g[H[i][0]+1].push_back({H[i][1]+1,L[i]});
g[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
dfs(1,0);
precompute();
decompose(1,-1);
for(int i=0;i<MAXK;i++)minh[i]=n+2;
for(int i=1;i<=n;i++)rankc[i]=n-rankc[i]+1;
for(int i=1;i<=n;i++)
{
minh[0]=0;
updated.push_back(0);
for(auto v:g[i])
{
if(rankc[v.first]>=rankc[i])continue;
if(v.second>k)continue;
dfs3(v.first,i,rankc[i],1,v.second);
dfs2(v.first,i,rankc[i],1,v.second);
}
for(auto u:updated)minh[u]=n+2;
}
if(ans>n)return -1;
return ans;
}
