//#include "race.h"
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
using namespace std;
vector<vector<pair<int, int>>>G;
int answ = 1e9 + 7, compSize, maxDep, maxMaxDep;
const int NN = 2e5 + 5;
unordered_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 (node_depth > 0) {
if (cur_depth[node_sum] == 0)
cur_depth[node_sum] = node_depth;
else
cur_depth[node_sum] = min(cur_depth[node_sum], node_depth);
if (depth[k - node_sum] != 0)
{
answ = min(answ, node_depth + 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[it.first] == 0)
depth[it.first] = it.second;
else
depth[it.first] = min(depth[it.first], it.second);
it.second = 0;
}
cur_depth.clear();
assert(!cur_depth.empty());
}
}
void centroid_decomposition()
{
queue<int>q;
q.push(0);
while (!q.empty())
{
int u = q.front();
q.pop();
int c = centroid(u);
solve(c, -1, 0, 0);
depth.clear();
assert(!depth.empty());
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;
}
