#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 2e5;
const int MAXK = 1e6 + 6;
int sz[MAXN];
vector<pair<int,int>> G[MAXN];
bitset<MAXN> viz;
void find_size(int u, int parent) {
sz[u] = 1;
for (auto v : G[u])
if (v.first != parent && !viz[v.first]) {
find_size(v.first, u);
sz[u] += sz[v.first];
}
}
int find_centroid(int u, int parent, int n) {
for (auto v : G[u])
if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
return find_centroid(v.first, u, n);
return u;
}
int ans = INF, k, best_prev[MAXK], best[MAXK], tree_ans;
vector<int> sums;
void min_self(int &a, int b) {
a = min(a, b);
}
void find_paths(int u, int parent, int sum, int depth) {
if (sum > k)
return;
sums.emplace_back(sum);
min_self(best[sum], depth);
min_self(tree_ans, best_prev[k - sum] + best[sum]);
if (sum == k)
return;
for (auto v : G[u])
if (v.first != parent && !viz[v.first])
find_paths(v.first, u, sum + v.second, depth + 1);
}
int solve_tree(int u) {
tree_ans = INF;
vector<int> all_sums;
for (auto v : G[u])
if (!viz[v.first]) {
find_paths(v.first, u, v.second, 1);
for (int s : sums) {
min_self(best_prev[s], best[s]);
best[s] = INF;
all_sums.emplace_back(s);
}
sums.clear();
}
for (int s : all_sums)
best_prev[s] = INF;
return tree_ans;
}
int build(int u, int parent) {
find_size(u, -1);
int c = find_centroid(u, -1, sz[u]);
viz[c] = true;
int ans = solve_tree(c);
for (auto v : G[c])
if (!viz[v.first])
ans = min(ans, build(v.first, c));
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; ++i) {
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
k = K;
for (int s = 1; s <= k; ++s)
best_prev[s] = best[s] = INF;
min_self(ans , build(0, -1));
if (ans == INF)
ans = -1;
return ans;
}
