#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define MAXN 200007
using namespace std;
vector<vector<pair<int,ll>>>T(MAXN);
bool used[MAXN];
int subtree[MAXN];
void subtreedfs(int node, int p=-1)
{
subtree[node]=1;
for(auto i:T[node]) if(!used[i.first] && i.first!=p)
{
subtreedfs(i.first,node);
subtree[node]+=subtree[i.first];
}
}
int getCentroid(int node, int subsz, int p=-1)
{
for(auto i:T[node]) if(i.first!=p && !used[i.first] && subtree[i.first]*2>subsz) return getCentroid(i.first,subsz,node);
return node;
}
ll depth[MAXN];
map<ll,int>m;
map<ll,bool>seen;
int k, ans=INT_MAX;
void dfs1(int node, int p, ll d, int d1)
{
if(seen[k-d]) ans=min(ans,d1+m[k-d]);
for(auto i:T[node]) if(i.first!=p && !used[i.first]) dfs1(i.first,node,d+i.second,d1+1);
}
void dfs2(int node, int p, ll d, int d1)
{
depth[node]=d;
if(seen[d]) m[d]=min(m[d],d1);
else
{
m[d]=d1;
seen[d]=true;
}
for(auto i:T[node]) if(i.first!=p && !used[i.first]) dfs2(i.first,node,d+i.second,d1+1);
}
void cenDec(int node)
{
subtreedfs(node);
int c=getCentroid(node,subtree[node]);
used[c]=true;
seen[0]=true;
m[0]=0;
for(auto i:T[c]) if(!used[i.first])
{
dfs1(i.first,c,i.second,1);
dfs2(i.first,c,i.second,1);
}
m.clear();
seen.clear();
for(auto i:T[c]) if(!used[i.first]) cenDec(i.first);
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++)
{
T[H[i][0]].emplace_back(H[i][1],L[i]);
T[H[i][1]].emplace_back(H[i][0],L[i]);
}
cenDec(1);
if(ans==INT_MAX) return -1;
return ans;
}
