//#include "race.h"
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
vector<vector<pair<int, int>>>G;
int answ = 1e9 + 7, compSize, maxDep, maxMaxDep;
const int NN = 2e5 + 5;
map<int, int>depth, cur_depth;
bool used[NN];
int sz[NN];
int k;
void dfs(int node, int parent)
{
sz[node] = 1;
for (auto i : G[node])
{
if (i.first == parent || used[i.first])
continue;
dfs(i.first, node);
sz[node] += sz[i.first];
}
}
int find_centroid(int node, int parent)
{
for (auto i : G[node])
{
if (i.first == parent || used[i.first])
continue;
if (sz[i.first] * 2 >= compSize)
return find_centroid(i.first, node);
}
return node;
}
int centroid(int u)
{
dfs(u, -1);
compSize = sz[u];
return find_centroid(u, -1);
}
void solve(int node, int parent, int node_depth, int node_sum)
{
if (node_sum > k)return;
if (cur_depth.count(node_sum) != 0)
cur_depth[node_sum] = min(cur_depth[node_sum], node_depth);
else
cur_depth[node_sum] = node_depth;
if (depth.count(k - node_sum) != 0)
answ = min(answ, cur_depth[node_sum] + depth[k - node_sum]);
for (auto i : G[node])
{
if (i.first == parent || used[i.first])
continue;
solve(i.first, node, node_depth + 1, node_sum + i.second);
if (parent != -1)
continue;
for (auto it : cur_depth)
{
if (!depth.count(it.first))
depth[it.first] = it.second;
else
depth[it.first] = min(depth[it.first], it.second);
}
cur_depth.clear();
}
}
void centroid_decomposition()
{
queue<int>q;
q.push(0);
while (!q.empty())
{
int u = q.front();
q.pop();
int c = centroid(u);
depth[0] = 0;
solve(c, -1, 0, 0);
depth.clear();
used[c] = true;
for (auto i : G[c])
{
if (used[i.first])
continue;
q.push(i.first);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
G.resize(N + 1);
for (int i = 0; i < N - 1; i++)
{
G[H[i][0]].push_back({ H[i][1], L[i] });
G[H[i][1]].push_back({ H[i][0], L[i] });
}
centroid_decomposition();
if (answ == 1e9 + 7)
return -1;
return answ;
}
