#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int n, k, depth[MAXN + 5], ans;
long long sum[MAXN + 5];
map<long long,int>m[MAXN + 5];
vector<pair<int,int>>v[MAXN + 5];
void _merge(int x, int y)
{
if(m[x].size() < m[y].size())swap(m[x], m[y]);
for(auto [key, value]: m[y])
{
if(m[x].count(k - key + 2 * sum[x]))
{
ans = min(ans, m[x][k - key + 2 * sum[x]] + value - 2 * depth[x]);
}
}
for(auto [key, value]: m[y])
{
if(!m[x].count(key))
{
m[x][key] = value;
}
else m[x][key] = min(m[x][key], value);
}
}
void dfsp(int node, int parent)
{
depth[node] = depth[parent] + 1;
for(auto i: v[node])
{
if(i.first == parent)continue;
sum[i.first] = sum[node] + i.second;
dfsp(i.first, node);
}
}
void dfs(int node, int parent)
{
for(auto i: v[node])
{
if(i.first == parent)continue;
dfs(i.first, node);
_merge(node, i.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N; k = K; ans = 1e9;
for(int i = 0; i < n - 1; i++)
{
v[H[i][0]].push_back({H[i][1], L[i]});
v[H[i][1]].push_back({H[i][0], L[i]});
}
depth[0] = -1;
dfsp(0, 0);
for(int i = 0; i < n; i++){
m[i][sum[i]] = depth[i];
//cout << i << " " << sum[i] << " " << depth[i] << endl;
}
dfs(0, 0);
if(ans == 1e9)ans = -1;
return ans;
}
