#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 7;
const int mxK = 1e6 + 7;
int n, k;
vector<int> cur_seg;
vector<pair<int,int>> sums, graph[mxN];
int dp[mxN], p[mxN], len[mxK];
bool vis[mxN];
void dfs(int u, int par) {
dp[u] = 1;
p[u] = par;
for (auto pr : graph[u]) {
int v = pr.first;
if (!vis[v] && v != par) {
dfs(v, u);
dp[u] += dp[v];
}
}
cur_seg.push_back(u);
}
int find_centroid(int x) {
cur_seg.clear();
dfs(x, -1);
for (int u : cur_seg) {
int max_subtree = cur_seg.size() - dp[u];
for (auto pr : graph[u]) {
int v = pr.first;
if (v != p[u] && !vis[v]) {
max_subtree = max(max_subtree, dp[v]);
}
}
if (max_subtree <= cur_seg.size() / 2) {
return u;
}
}
return x;
}
int ans = INT_MAX;
void find_min_path(int u, int par, int cnt, int sum) {
if (sum < k && len[k - sum]) {
ans = min(ans, cnt + len[k - sum]);
}
else if (sum == k) {
ans = min(ans, cnt);
}
if (sum > k) {
return;
}
for (auto pr : graph[u]) {
int v = pr.first, w = pr.second;
if (!vis[v] && v != par) {
find_min_path(v, u, cnt + 1, sum + w);
}
}
sums.push_back({sum, cnt});
}
void decompose(int x) {
int c = find_centroid(x);
vis[c] = true;
vector<int> reset;
for (auto pr : graph[c]) {
int v = pr.first, w = pr.second;
if (!vis[v]) {
sums.clear();
find_min_path(v, c, 1, w);
for (auto prr : sums) {
int sum = prr.first, cnt = prr.second;
if (!len[sum]) {
len[sum] = cnt;
}
else {
len[sum] = min(len[sum], cnt);
}
reset.push_back(sum);
}
}
}
for (auto sum : reset) {
len[sum] = 0;
}
for (auto pr : graph[c]) {
int v = pr.first;
if (!vis[v]) {
decompose(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
decompose(0);
return (ans == INT_MAX ? -1 : ans);
}
