#include "race.h"
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int NMAX=2e5;
vector<pair<int, int>> g[NMAX+1];
int sz[NMAX+1];
bool elim[NMAX+1];
inline void get_subtree_size(int nod, int par=-1)
{
sz[nod]=1;
for(auto &[copil, cost]:g[nod])
{
if(copil!=par && !elim[copil])
{
get_subtree_size(copil, nod);
sz[nod]+=sz[copil];
}
}
}
inline int find_centroid(int nod, int tree_size, int par=-1)
{
for(auto &[copil, cost]:g[nod])
{
if(copil!=par && !elim[copil])
{
if(sz[copil] * 2 > tree_size)
return find_centroid(copil, tree_size, nod);
}
}
return nod;
}
struct myHash
{
const int operator ()(const int &x) const{
return x^(x>>1);
}
};
map<int, int> minpath;
int ans=1e9;
int target;
///minpath[i]=nrmin de drumuri cu suma costurilor = i
void dfs(int nod, int par, int dist, int h, bool calc)
{
if(calc==1 && minpath[target-dist]!=0)
{
ans=min(ans, h+minpath[target-dist]);
}
if(calc==0)
{
if(minpath[dist]==0)minpath[dist]=h;
else minpath[dist]=min(minpath[dist], h);
}
for(auto &[copil, cost]:g[nod])
if(copil!=par && !elim[copil])
dfs(copil, nod, cost+dist, h+1, calc);
}
void decomp(int nod)
{
get_subtree_size(nod);
int centroid=find_centroid(nod, sz[nod]);
///fac ceva
minpath[0]=1;
for(auto &[copil, cost]:g[centroid])
if(!elim[copil])
{
dfs(copil, centroid, cost, 2, 1);
dfs(copil, centroid, cost, 2, 0);
}
minpath.clear();
elim[centroid]=1;
for(auto &[copil, cost]:g[centroid])
if(!elim[copil])
decomp(copil);
}
int best_path(int N, int K, int H[][2], int L[])
{
target=K;
for(int i=0; i<N-1; i++)
{
int x=H[i][0], y=H[i][1], z=L[i];
g[x].push_back({y, z});
g[y].push_back({x, z});
}
decomp(0);
if(ans==1e9)ans=1;
return ans-2;
}
