#include "race.h"
#include <bits/stdc++.h>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
vector<vector<pair<int, int>>>G;
int answ = 1e9, compSize, maxDep, maxMaxDep;
const int NN = 2e5 + 5;
unordered_map<int, set<int>>depth, cur_depth;
bool used[NN];
int sz[NN];
int k;
void merge_(set<int>&a, set<int>b)
{
for (auto i : b)
a.insert(i);
}
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_sum == k)
{
answ++;
return;
}
if (node_depth > 0)
{
cur_depth[node_sum].insert(node_depth);
if (!depth[k - node_sum].empty())
{
answ = min(answ, node_depth + *depth[k - node_sum].begin());
}
}
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)
{
merge_(depth[it.first], it.second);
it.second.clear();
}
}
}
void centroid_decomposition()
{
queue<int>q;
q.push(0);
while (!q.empty())
{
int u = q.front();
q.pop();
int c = centroid(u);
maxDep = 0;
maxMaxDep = 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)
return -1;
return answ;
}
