#include"race.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 2e5+5;
vector<pll>g[sz];
ll vis[sz], lev[sz], p[30][sz], dis[sz];
void dfs(ll node, ll par)
{
for(auto [u, w] : g[node])
{
if(u == par)
continue;
p[0][u] = node;
lev[u] = lev[node] + 1;
dis[u] = dis[node] + w;
dfs(u, node);
}
}
ll jump(ll x, ll k)
{
for(ll i = 0; i < 26; i++)
{
if((k >> i) & 1)
x = p[i][x];
}
return x;
}
ll lca(ll x, ll y)
{
if(lev[x] > lev[y])
swap(x, y);
ll d = lev[y] - lev[x];
y = jump(y, d);
if(x == y)
return x;
else
{
for(ll i = 25; i >= 0; i--)
{
if(p[i][x] != p[i][y])
{
x = p[i][x];
y = p[i][y];
}
}
return p[0][x];
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ll n, k, i, j, x, y, z;
n = N;
k = K;
for(i = 0; i < n - 1; i++)
{
x = H[i][0];
y = H[i][1];
z = L[i];
x++;
y++;
g[x].pb({y, z});
g[y].pb({x, z});
}
dfs(1, 1);
for(i = 1; i < 26; i++)
{
for(j = 1; j <= n; j++)
p[i][j] = p[i-1][p[i-1][j]];
}
ll ans = INT_MAX;
for(i = 1; i <= n; i++)
{
for(j = i + 1; j <= n; j++)
{
ll a = lca(i, j);
ll ds = dis[i] + dis[j] - 2 * dis[a];
if(ds == k)
ans = min(ans, lev[i] + lev[j] - 2 * lev[a]);
}
}
if(ans == LLONG_MAX)
return -1;
else
return ans;
}
