// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 200005, K = 1e6 + 6;
int n, k, id;
vector<pair<int, int>> g[N];
int sz[N], cnt[K], call_id[K];
bool visited[N];
int get_min_cnt(int v) {
if (v == 0)
return 0;
if (v < 0 or k < v or call_id[v] != id)
return 1e9;
return cnt[v];
}
void set_min_cnt(int v, int c) {
if (v < 0 or k < v)
return;
cnt[v] = min(get_min_cnt(v), c);
call_id[v] = id;
}
void compute_size(int u, int p) {
sz[u] = 1;
for (auto [v, _] : g[u])
if (v != p and not visited[v]) {
compute_size(v, u);
sz[u] += sz[v];
}
}
int get_centroid(int u, int p, int n) {
for (auto [v, _] : g[u])
if (v != p and not visited[v] and n < 2 * sz[v])
return get_centroid(v, u, n);
return u;
}
int get_cnt(int u, int p, bool count_flag, int sum, int depth) {
int ans = 1e9;
if (count_flag)
set_min_cnt(sum, depth);
else ans = min(ans, get_min_cnt(k - sum) + depth);
for (auto [v, l] : g[u])
if (v != p and not visited[v])
ans = min(ans, get_cnt(v, u, count_flag, sum + l, depth + 1));
return ans;
}
int build(int u) {
compute_size(u, -1);
int centroid = get_centroid(u, -1, sz[u]);
visited[centroid] = true;
int ans = 1e9;
++id;
for (auto [v, l] : g[centroid])
if (not visited[v]) {
ans = min(ans, get_cnt(v, centroid, false, l, 1));
get_cnt(v, centroid, true, l, 1);
}
for (auto [v, _] : g[centroid])
if (not visited[v])
ans = min(ans, build(v));
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i + 1 < n; ++i) {
g[H[i][0]].emplace_back(H[i][1], L[i]);
g[H[i][1]].emplace_back(H[i][0], L[i]);
}
int ans = build(0);
if (ans >= n)
ans = -1;
return ans;
}
// int main() {
// ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
// int h[][2]{
// {0, 1},
// {0, 2},
// {2, 3},
// {3, 4},
// {4, 5},
// {0, 6},
// {6, 7},
// {6, 8},
// {8, 9},
// {8, 10}
// };
// int l[]{
// 3, 4, 5, 4, 6, 3, 2, 5, 6, 7
// };
// cout << best_path(11, 12, h, l) << '\n';
// return 0;
// }
